File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids

TitleEfficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids
Authors
Issue Date2000
PublisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgor
Citation
Journal Of Algorithms, 2000, v. 34 n. 2, p. 337-369 How to Cite?
AbstractIn a rectangular grid, given two sets of nodes, script capital L sign (sources) and script T sign (sinks), of size N/2 each, the disjoint paths (DP) problem is to connect as many nodes in script capital L sign to the nodes in script T sign using a set of "disjoint" paths. (Both edge-disjoint and vertex-disjoint cases are considered in this paper.) Note that in this DP problem, a node in script capital L sign can be connected to any node in script T sign. Although in general the sizes of script capital L sign and script T sign do not have to be the same, algorithms presented in this paper can also find the maximum number of disjoint paths pairing nodes in script capital L sign and script T sign. We use the network flow approach to solve this DP problem. By exploiting all the properties of the network, such as planarity and regularity of a grid, integral flow, and unit capacity source/sink/flow, we can optimally compress the size of the working grid (to be defined) from O(N2) to U(N1.5) and solve the problem in O(N2.5) time for both the edge-disjoint and vertex-disjoint cases, an improvement over the straightforward approach which takes O(N3) time. © 2000 Academic Press.
Persistent Identifierhttp://hdl.handle.net/10722/89141
ISSN
2011 Impact Factor: 0.5
2012 SCImago Journal Rankings: 0.469
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorChan, WTen_HK
dc.contributor.authorChin, FYLen_HK
dc.date.accessioned2010-09-06T09:52:54Z-
dc.date.available2010-09-06T09:52:54Z-
dc.date.issued2000en_HK
dc.identifier.citationJournal Of Algorithms, 2000, v. 34 n. 2, p. 337-369en_HK
dc.identifier.issn0196-6774en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89141-
dc.description.abstractIn a rectangular grid, given two sets of nodes, script capital L sign (sources) and script T sign (sinks), of size N/2 each, the disjoint paths (DP) problem is to connect as many nodes in script capital L sign to the nodes in script T sign using a set of "disjoint" paths. (Both edge-disjoint and vertex-disjoint cases are considered in this paper.) Note that in this DP problem, a node in script capital L sign can be connected to any node in script T sign. Although in general the sizes of script capital L sign and script T sign do not have to be the same, algorithms presented in this paper can also find the maximum number of disjoint paths pairing nodes in script capital L sign and script T sign. We use the network flow approach to solve this DP problem. By exploiting all the properties of the network, such as planarity and regularity of a grid, integral flow, and unit capacity source/sink/flow, we can optimally compress the size of the working grid (to be defined) from O(N2) to U(N1.5) and solve the problem in O(N2.5) time for both the edge-disjoint and vertex-disjoint cases, an improvement over the straightforward approach which takes O(N3) time. © 2000 Academic Press.en_HK
dc.languageengen_HK
dc.publisherAcademic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgoren_HK
dc.relation.ispartofJournal of Algorithmsen_HK
dc.titleEfficient Algorithms for Finding the Maximum Number of Disjoint Paths in Gridsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0196-6774&volume=34&spage=337&epage=369&date=2000&atitle=Efficient+Algorithms+for+Finding+the+Maximum+Number+of+Disjoint+Paths+in+Gridsen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1006/jagm.1999.1054en_HK
dc.identifier.scopuseid_2-s2.0-0037520828en_HK
dc.identifier.hkuros47879en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0037520828&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume34en_HK
dc.identifier.issue2en_HK
dc.identifier.spage337en_HK
dc.identifier.epage369en_HK
dc.identifier.isiWOS:000084882600006-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridChan, WT=7403918060en_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats