Escaping a grid by edge-disjoint paths

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

doi:10.1007/s00453-003-1023-8

Escaping a grid by edge-disjoint paths

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

School of Continuing Education

Research output: Contribution to journal › Journal article › peer-review

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

Original language	English
Pages (from-to)	343-359
Number of pages	17
Journal	Algorithmica (New York)
Volume	36
Issue number	4
Early online date	9 May 2003
DOIs	https://doi.org/10.1007/s00453-003-1023-8
Publication status	Published - Aug 2003

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 9 Industry, Innovation, and Infrastructure

User-Defined Keywords

Design and analysis of algorithm
Graph algorithm

Access to Document

10.1007/s00453-003-1023-8

Cite this

@article{4ecb4c9b073c447c9ba9d26abdfe3886,

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, 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 0(n2) time, which is faster than all previous approaches. This problem finds applications in point-to-point delivery, VLSI reconfiguration, and package routing.",

keywords = "Design and analysis of algorithm, Graph algorithm",

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

note = "Publisher Copyright: {\textcopyright} 2003 Springer-Verlag New York Inc",

year = "2003",

month = aug,

doi = "10.1007/s00453-003-1023-8",

language = "English",

volume = "36",

pages = "343--359",

journal = "Algorithmica (New York)",

issn = "0178-4617",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - Escaping a grid by edge-disjoint paths

AU - Chan, Wun Tat

AU - Chin, Francis Y.L.

AU - Ting, Hing Fung

PY - 2003/8

Y1 - 2003/8

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, 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 0(n2) time, which is faster than all previous approaches. This problem finds 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, 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 0(n2) time, which is faster than all previous approaches. This problem finds applications in point-to-point delivery, VLSI reconfiguration, and package routing.

KW - Design and analysis of algorithm

KW - Graph algorithm

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

UR - https://link.springer.com/article/10.1007/s00453-003-1023-8#Abs1

U2 - 10.1007/s00453-003-1023-8

DO - 10.1007/s00453-003-1023-8

M3 - Journal article

AN - SCOPUS:0942279261

SN - 0178-4617

VL - 36

SP - 343

EP - 359

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 4

ER -

Escaping a grid by edge-disjoint paths

Abstract

UN SDGs

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this