Cited By
View all- Kfoury ASisson L(2020)Efficient reassembling of three-regular planar graphsJournal of Combinatorial Optimization10.1007/s10878-020-00555-739:4(1153-1207)Online publication date: 1-May-2020
Disjoint paths in sparse graphs
Pages 3558 - 3568
Abstract
We generalize all the results obtained for maximum integer multiflow and minimum multicut problems in trees by Garg, Vazirani and Yannakakis [N. Garg, V.V. Vazirani, M. Yannakakis, Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica 18 (1997) 3-20] to graphs with a fixed cyclomatic number, while this cannot be achieved for other classical generalizations of trees. We also introduce thek-edge-outerplanar graphs, a class of planar graphs with arbitrary (but bounded) tree-width that generalizes the cacti, and show that the integrality gap of the maximum edge-disjoint paths problem is bounded in these graphs.
References
[1]
M. Andrews, J. Chuzhoy, S. Khanna, L. Zhang, Hardness of the undirected edge-disjoint paths problem with congestion, in: Proceedings FOCS 05, 2005
[2]
Baker, B.S., Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM. v41. 153-180.
[3]
Baveja, A. and Srinivasan, A., Approximation algorithms for disjoint paths and related routing and packing problems. Math. Oper. Res. v25. 255-280.
[4]
Bentz, C., On the complexity of the multicut problem in bounded tree-width graphs and digraphs. Discrete Applied Mathematics. v156. 1908-1917.
[5]
Bentz, C., Edge disjoint paths and max integral multiflow/min multicut theorems in planar graphs. In: Electronic Notes in Discrete Mathematics, vol. 22. pp. 55-60.
[6]
Bienstock, D. and Monma, C., On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmica. v5. 93-109.
[7]
H.L. Bodlaender, Planar graphs with bounded treewidth, Technical Report RUU-CS-88-14, Utrecht University, The Netherlands, 1988
[8]
C¿linescu, G., Fernandes, C.G. and Reed, B., Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width. Journal of Algorithms. v48. 333-359.
[9]
Carmi, P., Erlebach, T. and Okamoto, Y., Greedy edge-disjoint paths in complete graphs. In: LNCS, vol. 2880. pp. 143-155.
[10]
C. Chekuri, S. Khanna, Edge disjoint paths revisited, in: Proceedings SODA 03, 2003
[11]
Chekuri, C., Khanna, S. and Shepherd, F.B., An O(n)-approximation and integrality gap for disjoint paths and UFP. Theory of Computing. v2. 137-146.
[12]
C. Chekuri, S. Khanna, B. Shepherd, Edge-disjoint paths in planar graphs, in: Proceedings 45th IEEE FOCS, 2004
[13]
C. Chekuri, S. Khanna, B. Shepherd, Multicommodity flow, well-linked terminals, and routing problems, in: Proceedings STOC 05, 2005
[14]
C. Chekuri, S. Khanna, F.B. Shepherd, Edge-disjoint paths in planar graphs with constant congestion, in: Proceedings STOC 06, 2006
[15]
C. Chekuri, S. Khanna, F.B. Shepherd, A note on multiflows and treewidth, Algorithmica (2007) (in press). Available online at: http://dx.doi.org/10.1007/s00453-007-9129-z
[16]
Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D. and Yannakakis, M., The complexity of multiterminal cuts. SIAM Journal on Computing. v23. 864-894.
[17]
Downey, R.G. and Fellows, M.R., Parameterized Complexity. 1999. Springer-Verlag, New York.
[18]
Erlebach, T., Approximation algorithms and complexity results for path problems in trees of rings. In: LNCS, vol. 2136. pp. 351-362.
[19]
Even, S., Itai, A. and Shamir, A., On the complexity of timetable and multicommodity flow problems. SIAM Journal on Computing. v5. 691-703.
[20]
Ford, L.R. and Fulkerson, D.R., Maximal flow through a network. Canadian Journal of Mathematics. v8. 339-404.
[21]
Frank, A., Packing paths, circuits and cuts-a survey. In: Korte, B., Lovász, L., Prömel, H.J., Schrijver, A. (Eds.), Algorithms and combinatorics, vol. 9. Springer-Verlag, Berlin. pp. 47-100.
[22]
Frank, A., Edge-disjoint paths in planar graphs. Journal of Combinatorial Theory, Series B. v39. 164-178.
[23]
Frieze, A., Edge-disjoint paths in expander graphs. SIAM Journal on Computing. v30. 1790-1801.
[24]
Garg, N., Vazirani, V.V. and Yannakakis, M., Approximate max-flow min-(multi)cut theorems and their applications. SIAM Journal on Computing. v25. 235-251.
[25]
Garg, N., Vazirani, V.V. and Yannakakis, M., Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica. v18. 3-20.
[26]
A.M.H. Gerards, B. Shepherd, Preselecting homotopies for the weighted disjoint paths problem, (1993) Manuscript Available at: http://www.math.mcgill.ca/~bshepherd/PS/homotopy.ps
[27]
Hartvigsen, D., The planar multiterminal cut problem. Discrete Applied Mathematics. v85. 203-222.
[28]
J. Kleinberg, Approximation Algorithms for Disjoint Paths Problems, Ph.D Thesis, MIT, Cambridge, MA, 1996
[29]
J. Kleinberg, í¿. Tardos, Disjoint paths in densely embedded graphs, in: Proceedings 36th IEEE FOCS, 1995, pp. 52-61
[30]
Kleinberg, J. and Tardos, í¿., Approximations for the disjoint paths problem in high-diameter planar networks. Journal of Computer and System Sciences. v57. 61-73.
[31]
S. Kolliopoulos, C. Stein, Approximating disjoint-paths using greedy algorithms and packing integer programs, in: Proceedings IPCO 98, 1998
[32]
Kolman, P., A note on the greedy algorithm for the unsplittable flow problem. Information Processing Letters. v88. 101-105.
[33]
P. Kolman, C. Scheideler, Improved bounds for the unsplittable flow problem, in: Proceedings SODA 02, 2002, pp. 184-193
[34]
Korach, E. and Penn, M., A fast algorithm for maximum integral two-commodity flow in planar graphs. Discrete Applied Mathematics. v47. 77-83.
[35]
Kruskal, J.B., On the shortest spanning subtree of a graph and traveling salesman problem. Proceedings of the American Mathematical Society. v7. 48-50.
[36]
Marx, D., Eulerian disjoint paths problem in grid graphs is NP-complete. Discrete Applied Mathematics. v143. 336-341.
[37]
Middendorf, M. and Pfeiffer, F., On the complexity of the disjoint paths problem. Combinatorica. v13. 97-107.
[38]
Nishizeki, T., Vygen, J. and Zhou, X., The edge-disjoint paths problem is NP-complete for series-parallel graphs. Discrete Applied Mathematics. v115. 177-186.
[39]
K. Obata, Approximate max-integral-flow/min-multicut theorems, in: Proceedings STOC 04, 2004
[40]
Okamura, H. and Seymour, P.D., Multicommodity flows in planar graphs. Journal of Combinatorial Theory, Series B. v31. 75-81.
[41]
Raghavan, P., Probabilistic construction of deterministic algorithms: Approximating packing integer programs. Journal of Computer and System Sciences. v37. 130-143.
[42]
S. Rao, S. Zhou, Edge disjoint paths in moderately connected graphs, in: Proceedings ICALP 06, 2006, pp. 202-213
[43]
Robertson, N. and Seymour, P.D., Graphs minors XIII: The disjoint paths problem. Journal of Combinatorial Theory Ser. B. v63. 65-110.
[44]
Robertson, N. and Seymour, P.D., Graph minors II: Algorithmic aspects of tree-width. Journal of Algorithms. v7. 309-322.
[45]
Tardos, í¿. and Vazirani, V.V., Improved bounds for the max-flow min-multicut ratio for planar and Kr,r-free graphs. Information Processing Letters. v47. 77-80.
- Disjoint paths in sparse graphs
Recommendations
Finding Disjoint Paths in Split Graphs
The well-known Disjoint Paths problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the vertices in each terminal pair are ...
Spanners in sparse graphs
A t-spanner of a graph G is a spanning subgraph S in which the distance between every pair of vertices is at most t times their distance in G. If S is required to be a tree then S is called a tree t-spanner of G. In 1998, Fekete and Kremer showed that ...
Induced Disjoint Paths in AT-free graphs
AbstractPaths P 1 , … , P k are mutually induced if any two distinct P i and P j have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to decide if a graph G with k pairs ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © Elsevier B.V. © 2009.
Publisher
Elsevier Science Publishers B. V.
Netherlands
Publication History
Published: 01 October 2009
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Nov 2024
Other Metrics
Citations
Cited By
View all- Kfoury ASisson L(2020)Efficient reassembling of three-regular planar graphsJournal of Combinatorial Optimization10.1007/s10878-020-00555-739:4(1153-1207)Online publication date: 1-May-2020
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in