Publications   email: klein@cs.brown.edu

• Steiner tree in planar graphs: An O(n log n) approximation scheme with singly-exponential dependence on epsilon (pdf, bibtex)
  Glencora Borradaile,  Philip N. Klein, and Claire Mathieu
  Proceedings of the 10th International Workshop on Algorithms and Data Structures (2007), pp. 275-286.



• A polynomial-time approximation scheme for Steiner tree in planar graphs (pdf, bibtex)
  Glencora Borradaile, Claire Kenyon-Mathieu, and Philip N. Klein
  Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (2007), pp. 1285-1294.

• A subset spanner for planar graphs, with application to subset TSP (pdf, bibtex)
  Philip N. Klein
  Proceedings, 38th ACM Symposium on Theory of Computing (2006), pp. 749-756.
  

• An O(n log n) algorithm for maximum st-flow in a directed planar graph (pdf,  pdf for full version, bibtex)
  Glencora Borradaile and Philip N. Klein
  Proceedings, 17th ACM-SIAM Symposium on Discrete Algorithms (2006), pp. 524-533.
  

• A linear-time approximation scheme for TSP for planar weighted graphs (pdf, pdf for full version, bibtex)
  Philip N. Klein
  Proceedings, 46th IEEE Symposium on Foundations of Computer Science  (2005), pp. 647--656.
  
  

• Multiple-source shortest paths in planar graphs
  Philip N. Klein
  Proceedings, 16th ACM-SIAM Symposium on Discrete Algorithms (2005), pp. 146-155
  

• Approximation through local optimality: designing networks with small degree (ps)
  Philip N. Klein, Radha Krishnan, Balaji Raghavachari, and R. Ravi
  Networks  44 (2004), pp. 203-215.
  Preliminary version appeared in Proceedings, Twelfth Annual Conference on Foundations of Software Technology and Theoretical Computer Science, published as Lecture Notes in Computer Science 652, R. Shyamasundar (ed.), Springer-Verlag, New York (1992), pp. 279-290.
  
  
• Recognition of shapes by editing their shock graphs (ps, bibtex)
  Thomas Sebastian, Philip N. Klein, and Benjamin Kimia
  IEEE Transactions on Pattern Matching and Machine Intelligence 26 (2004), pp. 550-571.

• Detecting race conditions in parallel programs that use semaphores (pdf, bibtex)
  Philip N. Klein, Hsueh-I Lu and Robert H.B. Netzer
  Algorithmica 35 (2003) pp. 321 - 345.
  

  based on Race-condition detection in parallel computation with semaphores (ps, bibtex)
  Philip N. Klein, Hsueh-I Lu and Robert H. B. Netzer
  Proceedings, European Symposium on Algorithms (1996).
  and on Detecting race conditions in parallel programs that use one semaphore (ps, bibtex)
  Philip N. Klein, Hsueh-I Lu and Robert H. B. Netzer
  Proceedings, Workshop on Algorithms and Data Structures (1993), pp. 471-482.
  

• On aligning curves (ps, bibtex)
  Thomas Sebastian, Philip N. Klein, and Benjamin Kimia
  IEEE Transactions on Pattern Matching and Machine Intelligence 25 (2003), pp. 116-125.
  

• Preprocessing an undirected planar network to enable fast approximate distance queries (pdf, bibtex)
  Proceedings, 13th ACM-SIAM Symposium on Discrete Algorithms (2002), pp. 820-827.
  
  
• Shock-based Indexing into Large Shape Databases (pdf, bibtex)
  Thomas Sebastian, Philip N. Klein, and Benjamin B. Kimia
  Proceedings, European Conference on Computer Vision, Volume III (2002), pp. 731-746.
  

• Recognition of shapes by editing shock graphs (pdf, bibtex)
  Thomas B. Sebastian, Philip N. Klein, and Benjamin B. Kimia
  Proceedings, International Conference on Computer Vision (2001), pp. 755-762.
  
  
• Alignment-based recognition of shape outlines (pdf, bibtex)
  Thomas B. Sebastian, Philip N. Klein, and Benjamin B. Kimia
  International Workshop on Visual Form (2001), pp. 606-618.
  
  
• Shape matching using edit-distance: an implementation (pdf, bibtex)
  Philip N. Klein, Thomas B. Sebastian and Benjamin B. Kimia
  12th ACM-SIAM Symposium on Discrete Algorithms (2001), pp. 781-790.
  

• Using router stamping to identify the source of IP packets (pdf, bibTex)
  Thomas Doeppner, Philip N. Klein, and Andrew Koyfman
  7th ACM Conference on Computer and Communication Security (2000), pp. 184-189.
  
  
• Constructing 2D curve atlases (pdf, bibTex)
  Thomas Sebastian, Joseph J. Crisco, Philip N. Klein, and Benjamin Kimia
  Proceedings, IEEE Workshop on Mathematical Methods in Biomedical Image Analysis (2000), pp. 70-77.
  
  
• A Tree-edit-distance algorithm for comparing simple, closed shapes (ps, bibTex)
  Philip N. Klein, Srikanta Tirthapura, Daniel Sharvit, and Ben Kimia
  Proceedings, ACM-SIAM Symposium on Discrete Algorithms (2000), pp. 696-704.
  
  
• Finding the closest lattice vector when it's unusually close (ps, bibTex)
  Philip N. Klein
  Proceedings, ACM-SIAM Symposium on Discrete Algorithms (2000), pp. 937-941.
  

• Better rounding algorithms for a geometric embedding relaxation of minimum multiway cut (ps, bibTex)
  David R. Karger, Philip N. Klein, Cliff Stein, Mikkel Thorup, and Neal E. Young
  Proceedings, ACM Symposium on Theory of Computing (1999), 668 - 678.
  
  
• On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms (pdf, bibTex)
  Philip N. Klein and Neal E. Young
  Proceedings, Integer Programming and Combinatorial Optimization (1999), pp. 320-327.
  

• A fully dynamic approximation scheme for shortest path problems in planar graphs (ps, bibTex)
  Philip N. Klein and Sairam Subramanian
  Algorithmica 23 (1998), pp. 235-249.
  Preliminary version appeared in Proceedings, Workshop on Algorithms and Data Structures (1993), pp. 442-451.
  
  
• Indexing based on edit-distance matching of shape graphs (ps, bibTex)
  Srikanta Tirtapura, Daniel Sharvit, Philip N. Klein, and Benjamin Kimia
  Proceedings, SPIE International Symposium on Voice, Video, and Data Communications (1998), pp. 25-36.
  
  
• Space-efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs (ps, bibTex)
  Philip N. Klein and Hsueh-I Lu
  Proceedings, 9th International Symposium on Algorithms and Computation (1998), pp. 387-396.
  
  
• Computing the edit distance between unrooted ordered trees (ps, bibTex)
  Philip N. Klein
  Proceedings, 6th European Symposium on Algorithms (1998), pp. 91-102.
  
  
• A polynomial-time approximation scheme for weighted planar graph TSP (ps, bibTex)
  Sanjeev Arora, Michelangelo Grigni, David Karger, Philip N. Klein, and Andrzej Woloszyn
  Proceedings, 9th SIAM Symposium on Discrete Algorithms (1998), pp. 33-41.
  

• Approximation algorithms for Steiner and directed multicuts (ps, bibTex)
  Philip Klein, Serge Plotkin, Satish Rao, and Éva Tardos
  Journal of Algorithms 22 (1997), pp. 241-269.
  
  
• Faster shortest-path algorithms for planar graphs (ps, bibTex)
  Monika Rauch, Philip N. Klein, Satish Rao, and Sairam Subramanian
  Journal of Computer and System Sciences 55 (Special Issue on Selected Papers from 1994 STOC) (1997), pp. 3-23.
  Preliminary version appeared in Proceedings, 26th Symposium on Theory of Computing (1994), pp. 27-37.
  
  
• A randomized parallel algorithm for single-source shortest paths (ps, bibTex)
  Philip N. Klein and Sairam Subramanian
  Journal of Algorithms 25 (1997), pp. 205-220.
  Preliminary version appeared as ``A parallel randomized approximation scheme for shortest paths,'' Proceedings, 24th Symposium on Theory of Computing (1992), pp. 750-758.
  

• Efficient parallel algorithms for chordal graphs (ps, bibTex)
  Philip N. Klein
  SIAM J. Comput. 25 (1996), pp. 797-827.
  Preliminary version appeared in Proceedings, 29th Annual IEEE Symposium on Foundations of Computer Science (1988), pp. 150-161.
  
  
• Efficient Approximation Algorithms for Semidefinite Programs Arising from MAXCUT and COLORING (ps, bibTex)
  Philip N. Klein and Hsueh-I Lu
  Proceedings, 28th ACM Symposium on Theory of Computing, pp. 338-347 (1996).
  
  
• Finding minimum spanning forests in logarithmic time and linear work using random sampling (ps, bibTex)
  Richard Cole, Philip N. Klein, and Robert E. Tarjan
  Proceedings, 8th ACM Symposium on Parallel Algorithms and Architectures (1996), pp. 243-250.
  

• A randomized linear-time algorithm for finding a minimum spanning tree (ps, bibTex)
  David Karger, Philip N. Klein, and Robert E. Tarjan
  Journal of the ACM 42 (1995), pp. 321-328.
  Preliminary version appeared in Proceedings, 26th Symposium on Theory of Computing (1994), pp. 9-15.
  
  
• A nearly best-possible approximation algorithm for node-weighted Steiner trees (bibtex)
  Philip N. Klein and R. Ravi
  Journal of Algorithms 19 (1995), pp. 104-115.
  Preliminary version appeared in Proceedings, 3rd Symposium on Integer Programming and Combinatorial Optimization (1993), pp. 323-332.
  
  
• When trees collide: An approximation algorithm for the generalized Steiner tree problem on networks (pdf)
  Ajit Agrawal, Philip N. Klein, and R. Ravi,
  SIAM J. Comput. 24 (1995), pp. 440-456.
  Preliminary version appeared in Proceedings, 23nd ACM Symposium on Theory of Computing (1991), pp. 134-144.
  
  
• An approximate max-flow min-cut relation for multicommodity flow, with applications
  Philip N. Klein, Satish Rao, Ajit Agrawal, and R. Ravi
  Combinatorica 15 (1995), pp. 187-202.
  Preliminary version appeared as part of ``Approximation through multicommodity flow,'' Proceedings, 31st Annual Symposium on Foundations of Computer Science (1990), pp. 726-737.
  

• Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts (ps)
  Philip N. Klein, Serge Plotkin, Clifford Stein, and Éva Tardos
  SIAM J. Comput. 23 (1994), pp. 466-487.
  A preliminary version appeared as ``Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities,'' with Clifford Stein and Eva Tardos, Proceedings, 22nd ACM Symposium on Theory of Computing (1990), pp. 310-321.
  
  
• A data structure for bicategories, with application to speeding up an approximation algorithm (bibTex)
  Philip N. Klein
  Information Processing Letters 52 (1994), pp. 303-307.
  
  
• A linear-work parallel algorithm for finding a minimum spanning tree (ps)
  Philip N. Klein, Richard Cole and Robert E. Tarjan
  Proceedings, 6th ACM Symposium on Parallel Algorithms and Architectures (1994), pp. 11-15.
  

• Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs (bibTex)
  Ming-Yang Kao and Philip N. Klein
  Journal of Computer and System Sciences 47 (Special Issue on Selected Papers from 22nd STOC) (1993), pp. 459-500.
  Preliminary version appeared in Proceedings, 22nd ACM Symposium on Theory of Computing (1990), pp. 181-192.
  
  
• Parallelism, preprocessing, and reachability: a hybrid algorithm for directed graphs
  Philip N. Klein
  Journal of Algorithms 14 (1993), pp. 331-343.
  Preliminary version appeared in Proceedings of the AMS-IMS-SIAM Joint Summer Research Conference on Graphs and Algorithms (1987).
  
  
• The lattice structure of flow in planar graphs (bibTex)
  Samir Khuller, Joseph Naor, and Philip N. Klein
  SIAM Journal on Discrete Mathematics 6 (1993), pp. 477-490.
  
  
• A parallel algorithm for approximating the minimum cycle cover (ps)
  Philip N. Klein and Clifford Stein
  Algorithmica 9 (1993), pp. 23-31.
  
  
• A linear-processor, polylog-time algorithm for shortest paths in planar graphs (ps)
  Philip N. Klein and Sairam Subramanian
  Proceedings, 34th Symposium on Foundations of Computer Science (1993), pp. 259-270.
  
  
• Excluded minors, network decomposition, and multicommodity flow (ps, bibtex)
  Philip N. Klein, Serge Plotkin, and Satish Rao
  Proceedings, 25th ACM Symposium on Theory of Computing (1993), pp. 682-690.
  
  
• When cycles collapse: a general approximation technique for constrained two-connectivity problems (bibtex)
  Philip N. Klein and R. Ravi
  Proceedings, 3rd Symposium on Integer Programming and Combinatorial Optimization (1993) pp. 39-55.
  
  
• On Gazit and Miller's parallel algorithm for planar separators: achieving greater efficiency through random sampling (bibtex)
  Philip N. Klein
  Proceedings, 5th ACM Symposium on Parallel Algorithms and Architectures (1993), pp. 43-49.
  

• Ordering problems approximated: register sufficiency, single-processor scheduling and interval graph completion
  Ajit Agrawal, Philip N. Klein, and R. Ravi
  Proceedings, 18th International Conference on Automata, Languages, and Programming (1991), published as Lecture Notes in Computer Science, vol. 510, pp. 751-762. (Submitted to SIAM Journal on Discrete Mathematics.)
  

• On the time-space complexity of reachability queries for preprocessed graphs (pdf)
  Lisa Hellerstein, Philip N. Klein, and Robert Wilber
  Information Processing Letters 35 (1990), pp. 261-267.
  
  
• A parallel algorithm for eliminating cycles in undirected graphs (ps)
  Philip N. Klein and Clifford Stein
  Information Processing Letters 34 (1990), pp. 307-312.
  

• An efficient parallel algorithm for planarity (bibtex)
  Philip N. Klein and John H. Reif
  Journal of Computer and System Sciences (1988), pp. 190-246 (Special Issue on Selected Papers from 27th FOCS).
  A preliminary version appeared in Proceedings, 27th Annual IEEE Symposium on Foundations of Computer Science (1986), pp. 465-477.
  
  
• Parallel time acceptance of deterministic CFLs on an exclusive-write P-RAM
  Philip N. Klein and John H. Reif
  SIAM J. Comput. 17 (1988), pp. 463-485.
  

• Approximation Algorithms for Optimization Problems (ps)
  Philip N. Klein and Neal Young
  CRC Handbook on Algorithms and Theory of Computation, CRC (1998).
  
  
• Parallel algorithms for chordal graphs
  Philip N. Klein
  Synthesis of Parallel Algorithms, John H. Reif (ed.), Morgan-Kaufman (1993), pp. 341-407.
  
  
• Cutting down on fill using nested dissection: provably good elimination orderings
  Ajit Agrawal, Philip N. Klein, and R. Ravi
  Graph Theory and Sparse Matrix Computation, edited by A. George, J. Gilbert, and J. W. H. Liu, volume 56 in the IMA Volumes in Mathematics and its Applications, Springer-Verlag (1993), pp. 31-55.
  Preliminary version appeared as part of ``Approximation through multicommodity flow,'' with Ajit Agrawal, R. Ravi, and Satish Rao, Proceedings, 31th Annual Symposium on Foundations of Computer Science (1990), pp. 726-737.
  
  
• Approximating concurrent flow with uniform demands and capacities: an implementation
  James Borger, Sarah Kang, and Philip N. Klein
  Network Flows and Matching: First DIMACS Implementation Challenge, edited by D. S. Johnson and C. C. McGeoch, vol. 12 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society (1993), pp. 371-381.
  
  
• Invited review of "Fast approximation algorithms for multicommodity flow problems''
  Philip N. Klein
  Computing Reviews, July 1992.