Escaping a grid by edge-disjoint paths

Wun Tat Chan; Francis Y.L. Chin; Hing Fung Ting

Escaping a grid by edge-disjoint paths

Wun Tat Chan
, Francis Y.L. Chin
, Hing Fung Ting

School of Continuing Education

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

8 Citations (Scopus)

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(n²) time, which is faster than the previous approaches. This problem has applications in point-to-point delivery, VLSI reconfiguration and package routing.

Original language	English
Title of host publication	Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms, SODA 2000
Publisher	Association for Computing Machinery (ACM)
Pages	726-734
Number of pages	9
ISBN (Electronic)	9780898714531
Publication status	Published - 1 Feb 2000
Event	11th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2000 - San Francisco, United States Duration: 9 Jan 2000 → 11 Jan 2000 https://dl.acm.org/doi/proceedings/10.5555/338219 (Conference Proceedings)

Publication series

Name	Proceedings of the annual ACM-SIAM symposium on Discrete algorithms, SODA

Conference

Conference	11th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2000
Country/Territory	United States
City	San Francisco
Period	9/01/00 → 11/01/00
Internet address	https://dl.acm.org/doi/proceedings/10.5555/338219 (Conference Proceedings)

Access to Document

https://dl.acm.org/doi/10.5555/338219.338632

Cite this

@inproceedings{bb047d0aa2d7483ab0243c7a4b38d1b1,

title = "Escaping a grid by edge-disjoint paths",

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.",

author = "Chan, \{Wun Tat\} and Chin, \{Francis Y.L.\} and Ting, \{Hing Fung\}",

note = "Funding Information: The research is partially supported by a Hong Kong RGC grant 338/065/0022.; 11th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2000 ; Conference date: 09-01-2000 Through 11-01-2000",

year = "2000",

month = feb,

day = "1",

language = "English",

series = "Proceedings of the annual ACM-SIAM symposium on Discrete algorithms, SODA",

publisher = "Association for Computing Machinery (ACM)",

pages = "726--734",

booktitle = "Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms, SODA 2000",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.5555/338219",

}

Chan, WT, Chin, FYL & Ting, HF 2000, Escaping a grid by edge-disjoint paths. in Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms, SODA 2000. Proceedings of the annual ACM-SIAM symposium on Discrete algorithms, SODA, Association for Computing Machinery (ACM), pp. 726-734, 11th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2000, San Francisco, California, United States, 9/01/00. <https://dl.acm.org/doi/10.5555/338219.338632>

Escaping a grid by edge-disjoint paths. / Chan, Wun Tat; Chin, Francis Y.L.; Ting, Hing Fung.
Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms, SODA 2000. Association for Computing Machinery (ACM), 2000. p. 726-734 (Proceedings of the annual ACM-SIAM symposium on Discrete algorithms, SODA).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Escaping a grid by edge-disjoint paths

AU - Chan, Wun Tat

AU - Chin, Francis Y.L.

AU - Ting, Hing Fung

N1 - Funding Information: The research is partially supported by a Hong Kong RGC grant 338/065/0022.

PY - 2000/2/1

Y1 - 2000/2/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0033902898

M3 - Conference proceeding

AN - SCOPUS:0033902898

T3 - Proceedings of the annual ACM-SIAM symposium on Discrete algorithms, SODA

SP - 726

EP - 734

BT - Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms, SODA 2000

PB - Association for Computing Machinery (ACM)

T2 - 11th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2000

Y2 - 9 January 2000 through 11 January 2000

ER -

Escaping a grid by edge-disjoint paths

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this