File Download
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Escaping a grid by edge-disjoint paths
Title | Escaping a grid by edge-disjoint paths |
---|---|
Authors | |
Keywords | Mathematics computers |
Issue Date | 2000 |
Publisher | Society 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? |
Abstract | We 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 Identifier | http://hdl.handle.net/10722/45612 |
ISSN |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, WunTat | en_HK |
dc.contributor.author | Chin, Francis YL | en_HK |
dc.contributor.author | Ting, HingFung | en_HK |
dc.date.accessioned | 2007-10-30T06:30:17Z | - |
dc.date.available | 2007-10-30T06:30:17Z | - |
dc.date.issued | 2000 | en_HK |
dc.identifier.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 | en_HK |
dc.identifier.issn | 1071-9040 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/45612 | - |
dc.description.abstract | We 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.extent | 938420 bytes | - |
dc.format.extent | 5052 bytes | - |
dc.format.extent | 2010 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.format.mimetype | text/plain | - |
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 Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms | en_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.subject | Mathematics computers | en_HK |
dc.title | Escaping a grid by edge-disjoint paths | en_HK |
dc.type | Conference_Paper | en_HK |
dc.identifier.email | Chin, Francis YL:chin@cs.hku.hk | en_HK |
dc.identifier.email | Ting, HingFung:hfting@cs.hku.hk | en_HK |
dc.identifier.authority | Chin, Francis YL=rp00105 | en_HK |
dc.identifier.authority | Ting, HingFung=rp00177 | en_HK |
dc.description.nature | published_or_final_version | en_HK |
dc.identifier.scopus | eid_2-s2.0-0033902898 | en_HK |
dc.identifier.hkuros | 50414 | - |
dc.identifier.spage | 726 | en_HK |
dc.identifier.epage | 734 | en_HK |
dc.identifier.scopusauthorid | Chan, WunTat=7403918060 | en_HK |
dc.identifier.scopusauthorid | Chin, Francis YL=7005101915 | en_HK |
dc.identifier.scopusauthorid | Ting, HingFung=7005654198 | en_HK |
dc.identifier.issnl | 1071-9040 | - |