Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Efficient algorithms for finding disjoint paths in grids
Title  Efficient algorithms for finding disjoint paths in grids 

Authors  
Keywords  Mathematics computers 
Issue Date  1997 
Publisher  Society for Industrial and Applied Mathematics. 
Citation  Proceedings Of The Annual AcmSiam Symposium On Discrete Algorithms, 1997, p. 454463 How to Cite? 
Abstract  The reconfiguration problem on VLSI/WSI processor arrays in the presence of faulty processors can be stated as the following integral multisource routing problem: Given a set of N nodes (faulty processors or sources) in an m×n rectangular grid where m, n≤N, the problem to be solved is to connect the N nodes to distinct nodes at the grid boundary using a set of `disjoint' paths. This problem can be referred to as an escape problem which can be solved trivially in O(mnN) time. By exploiting all the properties of the network, planarity and regularity of a grid, integral flow, and unit capacity source/sink/flow, we can optimally compress the size of the grid from O(mn) to O(√mnN) and solve the problem in O(d√mnN), where d is the maximum number of disjoint paths found, for both the edgedisjoint and vertexdisjoint cases. In the worst case, d, m, n are O(N) and the result is O(N2.5). Note that this routing problem can also be solved with the same time complexity even if the disjoint paths have to be ended at another set of N nodes (sinks) in the grid instead of the grid boundary. 
Persistent Identifier  http://hdl.handle.net/10722/45568 
ISSN 
DC Field  Value  Language 

dc.contributor.author  Chan, WunTat  en_HK 
dc.contributor.author  Chin, Francis YL  en_HK 
dc.date.accessioned  20071030T06:29:22Z   
dc.date.available  20071030T06:29:22Z   
dc.date.issued  1997  en_HK 
dc.identifier.citation  Proceedings Of The Annual AcmSiam Symposium On Discrete Algorithms, 1997, p. 454463  en_HK 
dc.identifier.issn  10719040  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/45568   
dc.description.abstract  The reconfiguration problem on VLSI/WSI processor arrays in the presence of faulty processors can be stated as the following integral multisource routing problem: Given a set of N nodes (faulty processors or sources) in an m×n rectangular grid where m, n≤N, the problem to be solved is to connect the N nodes to distinct nodes at the grid boundary using a set of `disjoint' paths. This problem can be referred to as an escape problem which can be solved trivially in O(mnN) time. By exploiting all the properties of the network, planarity and regularity of a grid, integral flow, and unit capacity source/sink/flow, we can optimally compress the size of the grid from O(mn) to O(√mnN) and solve the problem in O(d√mnN), where d is the maximum number of disjoint paths found, for both the edgedisjoint and vertexdisjoint cases. In the worst case, d, m, n are O(N) and the result is O(N2.5). Note that this routing problem can also be solved with the same time complexity even if the disjoint paths have to be ended at another set of N nodes (sinks) in the grid instead of the grid boundary.  en_HK 
dc.format.extent  1239011 bytes   
dc.format.extent  5052 bytes   
dc.format.mimetype  application/pdf   
dc.format.mimetype  text/plain   
dc.language  eng  en_HK 
dc.publisher  Society for Industrial and Applied Mathematics.  en_HK 
dc.relation.ispartof  Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms  en_HK 
dc.rights  Creative Commons: Attribution 3.0 Hong Kong License   
dc.subject  Mathematics computers  en_HK 
dc.title  Efficient algorithms for finding disjoint paths in grids  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=10719040&volume=&spage=454&epage=463&date=1997&atitle=Efficient+algorithms+for+finding+disjoint+paths+in+grids  en_HK 
dc.identifier.email  Chin, Francis YL:chin@cs.hku.hk  en_HK 
dc.identifier.authority  Chin, Francis YL=rp00105  en_HK 
dc.description.nature  published_or_final_version  en_HK 
dc.identifier.scopus  eid_2s2.00030835060  en_HK 
dc.identifier.hkuros  23363   
dc.identifier.spage  454  en_HK 
dc.identifier.epage  463  en_HK 
dc.identifier.scopusauthorid  Chan, WunTat=7403918060  en_HK 
dc.identifier.scopusauthorid  Chin, Francis YL=7005101915  en_HK 