File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Efficient algorithms for finding disjoint paths in grids

TitleEfficient algorithms for finding disjoint paths in grids
Authors
KeywordsMathematics computers
Issue Date1997
PublisherSociety for Industrial and Applied Mathematics.
Citation
Proceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 1997, p. 454-463 How to Cite?
AbstractThe reconfiguration problem on VLSI/WSI processor arrays in the presence of faulty processors can be stated as the following integral multi-source 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 edge-disjoint and vertex-disjoint 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 Identifierhttp://hdl.handle.net/10722/45568
ISSN

 

DC FieldValueLanguage
dc.contributor.authorChan, WunTaten_HK
dc.contributor.authorChin, Francis YLen_HK
dc.date.accessioned2007-10-30T06:29:22Z-
dc.date.available2007-10-30T06:29:22Z-
dc.date.issued1997en_HK
dc.identifier.citationProceedings Of The Annual Acm-Siam Symposium On Discrete Algorithms, 1997, p. 454-463en_HK
dc.identifier.issn1071-9040en_HK
dc.identifier.urihttp://hdl.handle.net/10722/45568-
dc.description.abstractThe reconfiguration problem on VLSI/WSI processor arrays in the presence of faulty processors can be stated as the following integral multi-source 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 edge-disjoint and vertex-disjoint 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.extent1239011 bytes-
dc.format.extent5052 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypetext/plain-
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics.en_HK
dc.relation.ispartofProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectMathematics computersen_HK
dc.titleEfficient algorithms for finding disjoint paths in gridsen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1071-9040&volume=&spage=454&epage=463&date=1997&atitle=Efficient+algorithms+for+finding+disjoint+paths+in+gridsen_HK
dc.identifier.emailChin, Francis YL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, Francis YL=rp00105en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.scopuseid_2-s2.0-0030835060en_HK
dc.identifier.hkuros23363-
dc.identifier.spage454en_HK
dc.identifier.epage463en_HK
dc.identifier.scopusauthoridChan, WunTat=7403918060en_HK
dc.identifier.scopusauthoridChin, Francis YL=7005101915en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats