File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Escaping a grid by edge-disjoint paths

TitleEscaping a grid by edge-disjoint paths
Authors
Chan, WunTatChin, Francis YLTing, HingFung
KeywordsMathematics computers
Issue Date2000
PublisherSociety for Industrial and Applied Mathematics.
Citation
11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), San Francisco, CA, 9-11 January 2000. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, p. 726-734 How to Cite?
AbstractWe study the edge-disjoint escape problem in grids: Given a set of n sources in a two-dimensional grid, the problem is to connect all sources to the grid boundary using a set of n edge-disjoint paths. Different from the conventional approach that reduces the problem to network flow problem, we solve the problem by ensuring that no rectangles in the grid contain more sources than outlets, a necessary and sufficient condition for the existence of a solution. Based on this condition, we give a greedy algorithm which finds the paths in O(n2) time, which is faster than the previous approaches. This problem has applications in point-to-point delivery, VLSI reconfiguration and package routing.
Persistent Identifierhttp://hdl.handle.net/10722/45612
ISSN
1071-9040

 

DC FieldValueLanguage
dc.contributor.authorChan, WunTaten_HK
dc.contributor.authorChin, Francis YLen_HK
dc.contributor.authorTing, HingFungen_HK
dc.date.accessioned2007-10-30T06:30:17Z-
dc.date.available2007-10-30T06:30:17Z-
dc.date.issued2000en_HK
dc.identifier.citation11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), San Francisco, CA, 9-11 January 2000. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000, p. 726-734en_HK
dc.identifier.issn1071-9040en_HK
dc.identifier.urihttp://hdl.handle.net/10722/45612-
dc.description.abstractWe study the edge-disjoint escape problem in grids: Given a set of n sources in a two-dimensional grid, the problem is to connect all sources to the grid boundary using a set of n edge-disjoint paths. Different from the conventional approach that reduces the problem to network flow problem, we solve the problem by ensuring that no rectangles in the grid contain more sources than outlets, a necessary and sufficient condition for the existence of a solution. Based on this condition, we give a greedy algorithm which finds the paths in O(n2) time, which is faster than the previous approaches. This problem has applications in point-to-point delivery, VLSI reconfiguration and package routing.en_HK
dc.format.extent938420 bytes-
dc.format.extent5052 bytes-
dc.format.extent2010 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypetext/plain-
dc.format.mimetypetext/plain-
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics.en_HK
dc.relation.ispartofProceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithmsen_HK
dc.rights© 2000 Society for Industrial and Applied Mathematics. First Published in Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms in 2000, published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.subjectMathematics computersen_HK
dc.titleEscaping a grid by edge-disjoint pathsen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailChin, Francis YL:chin@cs.hku.hken_HK
dc.identifier.emailTing, HingFung:hfting@cs.hku.hken_HK
dc.identifier.authorityChin, Francis YL=rp00105en_HK
dc.identifier.authorityTing, HingFung=rp00177en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.scopuseid_2-s2.0-0033902898en_HK
dc.identifier.hkuros50414-
dc.identifier.spage726en_HK
dc.identifier.epage734en_HK
dc.identifier.scopusauthoridChan, WunTat=7403918060en_HK
dc.identifier.scopusauthoridChin, Francis YL=7005101915en_HK
dc.identifier.scopusauthoridTing, HingFung=7005654198en_HK
dc.identifier.issnl1071-9040-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats