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

✍ Scribed by Wun-Tat Chan; Francis Y.L. Chin

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 366 KB
• Volume: 34
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1999.1054

✦ Synopsis

In a rectangular grid, given two sets of nodes, S S sources and T T sinks , of size 2 Ž . each, the disjoint paths DP problem is to connect as many nodes in S S to the Ž nodes in T T using a set of ''disjoint'' paths. Both edge-disjoint and ¨ertex-disjoint . cases are considered in this paper. Note that in this DP problem, a node in S S can be connected to any node in T T. Although in general the sizes of S S and T T do not have to be the same, algorithms presented in this paper can also find the maximum number of disjoint paths pairing nodes in S S and T T. 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 Ž sourcersinkrflow, we can optimally compress the size of the working grid to be . Ž 2 . Ž 1.5 . Ž 2.5 . defined from O N to O N and solve the problem in O N time for both the edge-disjoint and vertex-disjoint cases, an improvement over the straightfor-Ž 3 . ward approach which takes O N time.