File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Escaping a grid by edge-disjoint paths

TitleEscaping a grid by edge-disjoint paths
Authors
Chan, WTChin, FYLTing, HF
KeywordsDesign And Analysis Of Algorithm
Graph Algorithm
Issue Date2003
PublisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htm
Citation
Algorithmica (New York), 2003, v. 36 n. 4, p. 343-359 How to Cite?
DOI: http://dx.doi.org/10.1007/s00453-003-1023-8
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, 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.
Persistent Identifierhttp://hdl.handle.net/10722/152313
ISSN
0178-4617
2021 Impact Factor: 0.909
2020 SCImago Journal Rankings: 0.647
ISI Accession Number ID
WOS:000182977000002
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChan, WTen_US
dc.contributor.authorChin, FYLen_US
dc.contributor.authorTing, HFen_US
dc.date.accessioned2012-06-26T06:37:07Z-
dc.date.available2012-06-26T06:37:07Z-
dc.date.issued2003en_US
dc.identifier.citationAlgorithmica (New York), 2003, v. 36 n. 4, p. 343-359en_US
dc.identifier.issn0178-4617en_US
dc.identifier.urihttp://hdl.handle.net/10722/152313-
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, 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.en_US
dc.languageengen_US
dc.publisherSpringer New York LLC. The Journal's web site is located at http://link.springer.de/link/service/journals/00453/index.htmen_US
dc.relation.ispartofAlgorithmica (New York)en_US
dc.subjectDesign And Analysis Of Algorithmen_US
dc.subjectGraph Algorithmen_US
dc.titleEscaping a grid by edge-disjoint pathsen_US
dc.typeArticleen_US
dc.identifier.emailChin, FYL:chin@cs.hku.hken_US
dc.identifier.emailTing, HF:hfting@cs.hku.hken_US
dc.identifier.authorityChin, FYL=rp00105en_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/s00453-003-1023-8en_US
dc.identifier.scopuseid_2-s2.0-0942279261en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0942279261&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume36en_US
dc.identifier.issue4en_US
dc.identifier.spage343en_US
dc.identifier.epage359en_US
dc.identifier.isiWOS:000182977000002-
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridChan, WT=7403918060en_US
dc.identifier.scopusauthoridChin, FYL=7005101915en_US
dc.identifier.scopusauthoridTing, HF=7005654198en_US
dc.identifier.issnl0178-4617-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats