DocumentCode
2386838
Title
An approximation algorithm for the disjoint paths problem in even-degree planar graphs
Author
Kleinberg, Jon
Author_Institution
Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
fYear
2005
fDate
23-25 Oct. 2005
Firstpage
627
Lastpage
636
Abstract
In joint work with Eva Tardos in 1995, we asked whether it was possible to obtain a polynomial-time, polylogarithmic approximation algorithm for the disjoint paths problem in the class of all even-degree planar graphs. This paper answers the question in the affirmative, by providing such an algorithm. The algorithm builds on recent work of C. Chekuri et al. (2004, 2005), who considered muting problems in planar graphs where each edge can carry up to two paths.
Keywords
computational complexity; graph theory; disjoint paths; even-degree planar graphs; muting problems; polynomial-time polylogarithmic approximation algorithm; Approximation algorithms; Design optimization; Graph theory; Joining processes; Optimized production technology; Polynomials; Routing; Tree graphs; Upper bound; Very large scale integration;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on
Print_ISBN
0-7695-2468-0
Type
conf
DOI
10.1109/SFCS.2005.18
Filename
1530754
Link To Document