File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1006/jagm.1999.1054
- Scopus: eid_2-s2.0-0037520828
- WOS: WOS:000084882600006
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids
Title | Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids |
---|---|
Authors | |
Issue Date | 2000 |
Publisher | Academic 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? |
Abstract | In 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 Identifier | http://hdl.handle.net/10722/89141 |
ISSN | 2011 Impact Factor: 0.5 2012 SCImago Journal Rankings: 0.469 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chan, WT | en_HK |
dc.contributor.author | Chin, FYL | en_HK |
dc.date.accessioned | 2010-09-06T09:52:54Z | - |
dc.date.available | 2010-09-06T09:52:54Z | - |
dc.date.issued | 2000 | en_HK |
dc.identifier.citation | Journal Of Algorithms, 2000, v. 34 n. 2, p. 337-369 | en_HK |
dc.identifier.issn | 0196-6774 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/89141 | - |
dc.description.abstract | In 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.language | eng | en_HK |
dc.publisher | Academic Press. The Journal's web site is located at http://www.elsevier.com/locate/jalgor | en_HK |
dc.relation.ispartof | Journal of Algorithms | en_HK |
dc.title | Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+Grids | en_HK |
dc.identifier.email | Chin, FYL:chin@cs.hku.hk | en_HK |
dc.identifier.authority | Chin, FYL=rp00105 | en_HK |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1006/jagm.1999.1054 | en_HK |
dc.identifier.scopus | eid_2-s2.0-0037520828 | en_HK |
dc.identifier.hkuros | 47879 | en_HK |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-0037520828&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 34 | en_HK |
dc.identifier.issue | 2 | en_HK |
dc.identifier.spage | 337 | en_HK |
dc.identifier.epage | 369 | en_HK |
dc.identifier.isi | WOS:000084882600006 | - |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Chan, WT=7403918060 | en_HK |
dc.identifier.scopusauthorid | Chin, FYL=7005101915 | en_HK |