Philip Klein's Publications
2007
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., Klein, P. N., and Mathieu, C. Steiner Tree in Planar Graphs: An O ( n log n ) Approximation Scheme with Singly-Exponential Dependence on Epsilon. WADS 2007, pp. 275-286.
2006
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 ]
2005
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. Multiple-source shortest paths in planar graphs. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2005), pp. 146-155. [ pdf ]
2004
Karger, D. R., Klein, P., Stein, C., Thorup, M., and Young, N. E. Rounding algorithms for a geometric embedding of minimum multiway cut. Mathematics of Operations Research 29, 3 (2004), 436-461. [ pdf ]
Klein, P. N., Krishnan, R., Raghavachari, B., and Ravi, R. Approximation algorithms for finding low-degree subgraphs. Networks 44 (2004), 203-215. [ pdf ]
Sebastian, T. B., Klein, P. N., and Kimia, B. B. Recognition of shapes by editing their shock graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 26, 5 (2004), 550-571. [ pdf ]
2003
Lu, H.-I., Klein, P. N., and Netzer, R. H. Detecting race conditions in parallel programs that use semaphores. Algorithmica 35 (2003), 321-345.
Sebastian, T. B., Klein, P. N., and Kimia, B. B. On aligning curves. IEEE Transactions on Pattern Analysis and Machine Intelligence 25, 1 (2003), 116-125. [ pdf ]
2002
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 ]
Sebastian, T. B., Klein, P. N., and Kimia, B. B. Shock-based indexing into large shape databases. In Proceedings of the Seventh European Conference on Computer Vision (2002), pp. 731-746. [ pdf ]
2001
Klein, P. N., Sebastian, T. B., and Kimia, B. B. Shape matching using edit-distance: an implementation. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (2001), pp. 781-790. [ pdf ]
Sebastian, T. B., Klein, P. N., and Kimia, B. B. Alignment-based recognition of shape outlines. In Proceedings of the Fourth International Workshop on Visual Form (2001), pp. 606-618. [ pdf ]
Sebastian, T. B., Klein, P. N., and Kimia, B. B. Recognition of shapes by editing shock graphs. In Proceedings of the Eighth International Conference On Computer Vision (2001), pp. 755-762. [ pdf ]
2000
Crisco, J. J., Klein, P. N., Kimia, B. B., and Sebastian, T. B. Constructing 2D curve atlases. In Proceedings of the IEEE Workshop on Mathematical Methods in Biomedical Image Analysis (2000), pp. 70-77. [ pdf ]
Doeppner, T. W., Klein, P. N., and Koyfman, A. Using router stamping to identify the source of IP packets. In Proceedings of the Seventh ACM Conference on Computer and Communications Security (2000), pp. 184-189. [ pdf ]
Klein, P. N. Finding the closest lattice vector when it's unusually close. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (2000), pp. 937-941. [ pdf ]
Klein, P. N., Tirthapura, S., Sharvit, D., and Kimia, B. B. A tree-edit-distance algorithm for comparing simple, closed shapes. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (2000), pp. 696-704. [ pdf ]
1999
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 ]
Klein, P. N., and Young, N. E. On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms. In Proceedings of the Integer Programming and Combinatorial Optimization (1999), pp. 320-327. [ pdf ]
1998
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 Young, N. E. Approximation algorithms for NP-hard optimization problems. In Handbook on Algorithms and Theory of Computation. CRC Press, 1998. [ 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 Subramanian, S. A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica 23 (1998), 235-249. [ 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 ]
Tirthapura, S., Sharvit, D., Klein, P. N., and Kimia, B. B. Indexing based on edit-distance matching of shape graphs. In Proceedings of the International Society for Optical Engineering (SPIE) Symposium on Voice, Video, and Data Communications (1998), pp. 25-36. [ postscript | pdf ]
1997
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 ]
1996
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 ]
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 ]
Klein, P. N., Lu, H.-I., and Netzer, R. H. B. Race-condition detection in parallel computation with semaphores. In Proceedings of the Fourth Annual European Symposium on Algorithms (1996), J. Díaz and M. Serna, Eds., Springer, pp. 445-459. [ pdf ]
1995
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 ]
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 ]
1994
Klein, P. N., Rauch, M., Rao, S., and Subramanian, S. Faster shortest-path algorithms. In Proceedings of the Twenty-Sixth Symposium on Theory of Computing (1994), pp. 27-37.
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 ]
Klein, P. N., and Tarjan, R. E. A randomized linear-time algorithm to find minimum spanning trees. In Proceedings of the Twenty-Sixth Symposium on Theory of Computing (1994), pp. 9-15.
1993
Agrawal, A., Klein, P. N., and Ravi, R. Cutting down on fill using nested dissection: provably good elimination orderings. In Graph Theory and Sparse Matrix Computation, A. George, J. Gilbert, and J. W. H. Liu, Eds. Springer-Verlag, 1993, pp. 31-55.
Kao, M.-Y., and Klein, P. N. Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs. Journal of Computer and Systems Sciences 47, 3 (1993), 459-500. [ 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., Kang, S., and Borger, J. Approximating concurrent flow with uniform demands and capacities: an implementation. In Network Flows and Matching: First DIMACS Implementation Challenge, D. S. Johnson and C. C. McGeoch, Eds. American Mathematical Society, 1993, pp. 371-381.
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., and Subramanian, S. A fully dynamic approximation scheme for shortest paths in planar graphs. In Proceedings of the Workshop on Algorithms and Data Structures (1993), pp. 442-451.
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 Subramanian, S. A linear-processor, polylog-time algorithm for shortest paths in planar graphs. In Proceedings of the Thirty-Fourth Symposium on Foundations of Computer Science (1993), pp. 259-270. [ pdf ]
Klein, P. N., and Ravi, R. A nearly best-possible approximation algorithm for node-weighted Steiner trees. In Proceedings of the Third Symposium on Integer Programming and Combinatorial Optimization (1993), pp. 323-332.
Klein, P. N., and Stein, C. A parallel algorithm for approximating the minimum cycle cover. Algorithmica 9 (1993), 23-31. [ pdf ]
Klein, P. N. Parallel algorithms for chordal graphs. In Synthesis of Parallel Algorithms, J. H. Reif, Ed. Morgan-Kaufman, 1993, pp. 341-407.
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.
Lu, H.-I., Klein, P. N., and Netzer, R. H. Detecting race conditions in parallel programs that use one semaphore. In Proceedings of the Workshop on Algorithms and Data Structures (1993), pp. 471-482.
1992
Klein, P. N., and Subramanian, S. A parallel randomized approximation scheme for shortest paths. In Proceedings of the Twenty-Fourth Symposium on Theory of Computing (1992), pp. 750-758.
Ravi, R., Raghavachari, B., and Klein, P. N. Approximation through local optimality: designing networks with small degree. In Proceedings of the Twelfth Annual Conference on Foundations of Software Technology and Theoretical Computer Science (1992), pp. 279-290.
1991
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 ]
Agrawal, A., Klein, P. N., and Ravi, R. When trees collide: An approximation algorithm for the generalized Steiner tree problem on networks. In Proccedings of the Twenty-Third ACM Symposium on Theory of Computing (1991), pp. 134-144.
1990
Agrawal, A., Klein, P. N., Rao, S., and Ravi, R. Approximation through multicommodity flow. In Proceedings of the Thirty-First Annual Symposium on Foundations of Computer Science (1990), pp. 726-737.
Hellerstein, L., Klein, P. N., and Wilber, R. On the time-space complexity of reachability queries for preprocessed graphs. Information Processing Letters 34 (1990), 307-312.
Kao, M.-Y., and Klein, P. N. Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs. In Proceedings of the Twenty-Second ACM Symposium on Theory of Computing (1990), pp. 181-192.
Klein, P. N., Stein, C., and Tardos, E. Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities. In Proceedings of the Twenty-Second ACM Symposium on Theory of Computing (1990), pp. 310-321.
Klein, P. N., and Stein, C. `A parallel algorithm for eliminating cycles in undirected graphs. Information Processing Letters 34 (1990), 307-312.
1988
Klein, P. N., and Reif, J. H. An efficient parallel algorithm for planarity. Journal of Computer and Systems Sciences 37, 2 (1988), 190-246.
Klein, P. N. Efficient parallel algorithms for chordal graphs. In Proceedings of the Twenty-Ninth Annual IEEE Symposium on Foundations of Computer Science (1988), pp. 150-161.
Klein, P. N., and Reif, J. H. Parallel time O(logn) acceptance of deterministic CFLs on an exclusive-write P-RAM. SIAM Journal on Computing 17 (1988), 463-485.
1989
Klein, P. N. Parallelism, preprocessing, and reachability: a hybrid algorithm for directed graphs. In Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graphs and Algorithms (1987), Contemporary Mathematics, pp. 129-143.
1986
Klein, P. N., and Reif, J. H. An efficient parallel algorithm for planarity. In Proceedings of the Twenty-Seventh Annual IEEE Symposium on Foundations of Computer Science (1986), pp. 465-477.
| Page Owner: Philip Klein | Last Modified: Sun Dec 3 15:45:10 2006 |