 |
Algorithms for Optimization Problems in Planar Graphs
The aim of this project is to develop algorithms for fundamental optimization problems on planar networks. Logistics problems on road maps and image processing are motivating application areas.
Project status: Active
Research Areas
| Combinatorial Optimization |
| Design and Analysis of Algorithms |
People
| Glencora Borradaile |
| Philip Klein |
| Claire Mathieu |
| Barbara J. Meier |
Publications
Borradaile, G., Kenyon-Mathieu, C., and Klein, P. A Polynomial-Time Approximation Scheme for Steiner Tree in Planar Graphs. In ACM-SIAM Symposium on Discrete Algorithms (New Orleans, Jan 2007), ACM-SIAM.
Borradaile, G., and Klein, P. N. An O(n log n) algorithm for maximum st-flow in a directed planar graph. In Symposium on Discrete Algorithms (2006), pp. 524-533. [ pdf ]
Klein, P. N. A subset spanner for planar graphs, with application to subset TSP. In Proceedings of the Thirty-Eighth ACM Symposium on Theory of Computing (2006), pp. 524-533. [ pdf ]
Klein, P. N. A linear-time approximation scheme for TSP for planar weighted graphs. In Proceedings of the Forty-Sixth IEEE Symposium on Foundations of Computer Science (2005), pp. 647-656. [ pdf ]
Klein, P. N. Preprocessing an undirected planar network to enable fast. In Proceedings of the Thirteenth Annual ACM-SIAM Symposium On Discrete Mathematics (2002), pp. 820-827. [ pdf ]
Arora, S., Grigni, M., Karger, D. R., Klein, P. N., and Woloszyn, A. A polynomial-time approximation scheme for weighted planar graph TSP. In Proceedings of the Symposium on Discrete Algorithms (1998), pp. 33-41. [ pdf ]
Klein, P. N., and Subramanian, S. A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica 23 (1998), 235-249. [ pdf ]
Henzinger, M. R., Klein, P. N., Rao, S., and Subramanian, S. Faster shortest-path algorithms for planar graphs. Journal of Computer and System Sciences 55, 1 (1997), 3-23. [ pdf ]
Khuller, S., Naor, J., and Klein, P. The lattice structure of flow in planar graphs. SIAM Journal on Discrete Mathematics 6, 3 (1993), 477-490. [ pdf ]
Klein, P. N. On Gazit and Miller's parallel algorithm for planar separators: achieving greater efficiency through random sampling. In Proceedings of the Fifth Annual ACM Symposium on Parallel Algorithms and Architectures (1993), pp. 43-49. [ pdf ]
| Page Owner: Webmaster | Last Modified: Mon Oct 23 14:57:09 2006 |