Graph Algorithms
Project status: Active
Research Areas
People
| Glencora Borradaile |
| Philip Klein |
| Claire Mathieu |
Publications
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., Krishnan, R., Raghavachari, B., and Ravi, R. Approximation algorithms for finding low-degree subgraphs. Networks 44 (2004), 203-215. [ 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 ]
Pizzonia, M., and Tamassia, R. Minimum Depth Graph Embedding. In Proceedings of the European Symposium on Algorithms (ESA 2000) (2000), Springer-Verlag. [ pdf ]
Di Battista, G., Tamassia, R., and Vismara, L. Output-Sensitive Reporting of Disjoint Paths. Algorithmica 23, 4 (1999), 302-340. [ pdf ]
Karger, D. R., Klein, P. N., Stein, C., Thorup, M., and Young, N. E. Rounding algorithms for a geometric embedding relaxation of minimum multiway cut. In Proceedings of the ACM Symposium on Theory of Computing (1999), pp. 668-678. [ 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 ]
Bertolazzi, P., Di Battista, G., Mannino, C., and Tamassia, R. Optimal Upward Planarity Testing of Single-Source Digraphs. SIAM Journal on Computing 27, 1 (1998), 132-169. [ pdf ]
Klein, P. N. Computing the edit-distance between unrooted ordered trees. In Proceedings of the European Symposium on Algorithms (1998), pp. 91-102. [ pdf ]
Klein, P. N., and Lu, H.-I. Space-efficient approximation algorithms for MAXCUT and COLORING semidefinite programs. In Proceedings of the Ninth International Symposium on Algorithms and Computation (1998), pp. 387-396. [ pdf ]
Cohen, R. F., and Tamassia, R. Combine and Conquer. Algorithmica 18 (1997), 342-362. [ 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 ]
Klein, P. N., Plotkin, S. A., Rao, S., and Tardos, E. Approximation Algorithms for Steiner and Directed Multicuts. Journal of Algorithms 22 (1997), 241-269. [ pdf ]
Klein, P. N., and Subramanian, S. A randomized parallel algorithm for single-source shortest paths. Journal of Algorithms 25 (1997), 205-220. [ pdf ]
Cole, R., Klein, P. N., and Tarjan, R. E. Finding minimum spanning forests in logarithmic time and linear work using random sampling. In Proceedings of the Symposium on Parallel Algorithms and Architecture (1996), pp. 243-250. [ pdf ]
Di Battista, G., and Tamassia, R. On-Line Maintenance of Triconnected Components with SPQR-Trees. Algorithmica 15 (1996), 302-318. [ pdf ]
Di Battista, G., and Tamassia, R. On-Line Planarity Testing. SIAM Journal on Computing 25, 5 (1996), 956-997. [ pdf ]
Di Battista, G., Tamassia, R., and Vismara, L. Output-Sensitive Reporting of Disjoint Paths. In Proceedings of the 2nd Annual International Conference on Computing and Combinatorics (1996), Springer-Verlag, pp. 81-91. [ pdf ]
Klein, P. N., and Lu, H.-I. Efficient approximation algorithms for semidefinite programs arising from MAX-CUT and COLORING. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (1996), pp. 338-347. [ pdf ]
Klein, P. N. Efficient parallel algorithms for chordal graphs. SIAM Journal on Computing 25, 4 (1996), 797-827. [ pdf ]
Tamassia, R. On-Line Planar Graph Embedding. Journal of Algorithms 21, 2 (1996), 201-239. [ pdf ]
Agrawal, A., Klein, P. N., and Ravi, R. When trees collide: An approximation algorithm for the generalized Steiner tree problem on networks. SIAM Journal on Computing 24 (1995), 440-456. [ pdf ]
Cohen, R. F., and Tamassia, R. Dynamic Expression Trees. Algorithmica 13 (1995), 245-265.
Karger, D. R., Klein, P. N., and Tarjan, R. E. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM 42 (1995), 321-328. [ pdf ]
Klein, P. N., Rao, S., Agrawal, A., and Ravi, R. An approximate max-flow min-cut relation for multicommodity flow, with applications. Combinatorica 15 (1995), 187-202.
Klein, P. N., and Ravi, R. A nearly best-possible approximation algorithm for node-weighted Steiner trees. Journal of Algorithms 19, 1 (1995), 104-115. [ pdf ]
Bertolazzi, P., Cohen, R. F., Di Battista, G., Tamassia, R., and Tollis, I. G. How to Draw a Series-Parallel Digraph. International Journal of Computational Geometry and Applications 4 (1994), 385-402.
Klein, P. N. A data structure for bicategories, with application to speeding up an approximation algorithm. Information Processing Letters 52, 6 (1994), 303-307. [ pdf ]
Klein, P. N., Plotkin, S., Stein, C., and Tardos, E. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM Journal on Computing 23 (1994), 466-487. [ pdf ]
Klein, P. N., Cole, R., and Tarjan, R. E. A linear-work parallel algorithm for finding a minimum spanning tree. In Proceedings of the Sixth ACM Symposium on Parallel Algorithms and Architectures (1994), pp. 11-15. [ pdf ]
Bertolazzi, P., Di Battista, G., Mannino, C., and Tamassia, R. Optimal Upward Planarity Testing of Single-Source Digraphs. In Proceedings of the 1st Annual European Symposium on Algorithms. Springer-Verlag, 1993, pp. 37-48.
Cohen, R. F., and Tamassia, R. Combine and Conquer: A General Technique for Dynamic Algorithms. In Proceedings of the 1st Annual European Symposium on Algorithms. Springer-Verlag, 1993, pp. 97-108.
Cohen, R. F., Sairam, S., Tamassia, R., and Vitter, J. S. Dynamic Algorithms for Optimization Problems in Bounded Tree-Width Graphs. In Proceedings of the Third Conference on Integer Programming and Combinatorial Optimization (1993), pp. 99-112.
Cohen, R. F., Di Battista, G., Kanevsky, A., and Tamassia, R. Reinventing the Wheel: an Optimal Data Structure for Connectivity Queries. In Proceedings of the 25th Annual ACM Symposium on Theory of Computing (1993), pp. 194-200.
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., Plotkin, S. A., and Rao, S. Excluded minors, network decomposition, and multicommodity flow. In Proceedings of the ACM Symposium on Theory of Computing (1993), pp. 682-690. [ 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 ]
Klein, P. N., and Stein, C. A parallel algorithm for approximating the minimum cycle cover. Algorithmica 9 (1993), 23-31. [ pdf ]
Klein, P. N. Parallelism, preprocessing, and reachability: a hybrid algorithm for directed graphs. Journal of Algorithms 14 (1993), 331-343.
Klein, P. N., and Ravi, R. When cycles collapse: A general approximation technique for constraind two-connectivity problems. In Proceedings of the Third Conference on Integer Programming & Combinatorial Optimization (IPCO) (1993), G. Rinaldi and L. Wolsey, Eds., pp. 39-55.
Tamassia, R., and Tollis, I. G. Reachability in Planar Digraphs with One Source and One Sink. Theoretical Computer Science 119 (1993), 331-343.
Eppstein, D., Italiano, G. F., Tamassia, R., Tarjan, R. E., Westbrook, J., and Yung, M. Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph. Journal of Algorithms 13, 1 (1992), 33-54.
Sairam, S., Tamassia, R., and Vitter, J. S. A Divide and Conquer Approach to Shortest Paths in Planar Layered Digraphs. In Proceedings of the 4th IEEE Symposium on Parallel and Distributed Processing (1992), pp. 176-183.
Agrawal, A., Klein, P. N., and Ravi, R. Ordering problems approximated: register sufficiency, single-processor scheduling and interval graph completion. In Proceedings of the Eighteenth International Conference on Automata, Languages, and Programming (1991), pp. 751-762. [ pdf ]
Cohen, R. F., and Tamassia, R. Dynamic Expression Trees and their Applications. In Proceedings of the 2nd ACM-SIAM Symposium on Discrete Algorithms (1991), pp. 52-61.
Kanevsky, A., Tamassia, R., Di Battista, G., and Chen, J. On-line Maintenance of the Four-Connected Components of a Graph. In Proceedings of the Annual IEEE Symposium on Foundations of Computer Science (1991), pp. 793-801.
Tamassia, R., and Vitter, J. S. Parallel transitive closure and point location in planar structures. SIAM Journal on Computing 20, 4 (1991), 708-725. [ pdf ]
Tamassia, R., and Tollis, I. G. Representations of Graphs on a Cylinder. SIAM Journal on Discrete Mathematics 4, 1 (1991), 139-149. [ pdf ]
Di Battista, G., and Tamassia, R. On-Line Graph Algorithms with SPQR-Trees. In Proceedings of the 17th International Colloquium on Automata, Languages and Programming (1990), M. S. Paterson, Ed., Springer-Verlag, pp. 598-611.
Eppstein, D., Italiano, G. F., Tamassia, R., Tarjan, R. E., Westbrook, J., and Yung, M. Maintenance of a minimum spanning forest in a dynamic planar graph. In Proceedings of the 1st ACM-SIAM Symposium on Discrete Algorithms (1990), pp. 1-11.
Tamassia, R., and Preparata, F. P. Dynamic maintenance of planar digraphs, with applications. Algorithmica 5 (1990), 509-527.
Di Battista, G., and Tamassia, R. Incremental Planarity Testing. In Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science (1989), pp. 436-441.
Tamassia, R., and Vitter, J. S. Optimal parallel algorithms for transitive closure and point location in planar structures. In Proceedings of the International Workshop on Discrete Algorithms and Complexity (Fukuoka, Japan, Nov 1989), Institute of Electronics, Information and Communication Engineers (IEICE), Tokyo, pp. 169-178.
Klein, P. N., and Reif, J. H. An efficient parallel algorithm for planarity. Journal of Computer and Systems Sciences 37, 2 (1988), 190-246.
Preparata, F. P., and Tamassia, R. Fully dynamic techniques for point location and transitive closure in planar structures. In Proceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science (1988), pp. 558-567.
Tamassia, R. A Dynamic Data Structure for Planar Graph Embedding. In Proceedings of the 15th International Colloquium on Automata, Languages and Programming (ICALP) (1988), T. Lepisto and A. Salomaa, Eds., Springer-Verlag, pp. 576-590.
Tamassia, R., and Tollis, I. G. Centipede Graphs and Visibility on a Cylinder. In Proceedings of the International Workshop on Graph Theoretic Concepts in Computer Science(WG '86 ) (Jun 1987), G. Tinhofer and G. Schmidt, Eds., Springer-Verlag, pp. 252-263.
| Page Owner: Webmaster | Last Modified: Mon Oct 23 14:57:09 2006 |