Escaping a grid by edge-disjoint paths

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

Research output: Contribution to journalArticlepeer-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, which reduces the problem to a network flow problem, we solve the problem by first ensuring that no rectangle 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 that finds the paths in O(n^2) time, which is faster than all previous approaches. This problem finds applications in point-to-point delivery, VLSI reconfiguration, and package routing.
Original languageEnglish
Pages (from-to)343 - 359
Number of pages17
JournalALGORITHMICA
Volume36
Issue number4
DOIs
Publication statusPublished - Aug 2007

Fingerprint

Dive into the research topics of 'Escaping a grid by edge-disjoint paths'. Together they form a unique fingerprint.

Cite this