2027

• Multiple-source shortest paths in planar graphs: an experimental study
  Philip N. Klein and Dragos Ristache
  Proceedings of the 29th Symposium on Algorithm Engineering and Experiments (ALENEX 2027), to appear.

2026

• Simple analysis of an algorithm for multiple-source shortest paths in planar graphs
  Philip N. Klein
  arXiv preprint arXiv:2610.02371, 2026.
• Routing in a road network using planar-graph lower bounds
  Philip N. Klein and Dragos Ristache
  Preprint, 2026.

2023

• Correlation clustering and two-edge-connected augmentation for planar graphs
  Philip N. Klein, Claire Mathieu, and Hang Zhou
  Algorithmica 85(10), pp. 3024-3057 (2023).

2021

• A quasipolynomial (2 + ε)-approximation for planar sparsest cut
  Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li
  Proceedings of the Fifty-Third Annual ACM Symposium on Theory of Computing (STOC 2021), 1056-1069.
• On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting
  Vincent Cohen-Addad, Philip N. Klein, Dániel Marx, Archer Wheeler, Christopher Wolfram
  Proceedings of the Second Symposium on Foundations of Responsible Computing (FORC 2021), 3:1-3:18.

2020

• The impact of highly compact algorithmic redistricting on the rural-versus-urban balance
  Archer Wheeler, Philip N. Klein
  Proceedings of the Twenty-Eighth International Conference on Advances in Geographic Information Systems (SIGSPATIAL 2020), 397-400.
• On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
  Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le
  Proceedings of the Sixty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020), 3:1-3:18.
• New hardness results for planar graph problems in p and an algorithm for sparsest cut
  Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
  Proceedings of the fifty-Second Annual ACM Symposium on Theory of Computing (STOC 2020), 996-1009.

2019

• Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
  Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
  SIAM Journal on Computing, 48(2), 644-667 (2019).
• A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs
  Amariah Becker, Philip N. Klein, Aaron Schild
  Proceedings of the Sixteenth International Symposium on Algorithms and Data Structures (WADS 2019), 99-111.
• Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems
  Eli Fox-Epstein, Philip Klein, Aaron Schild
  Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019), 1069-1088.

2018

• Balanced Centroidal Power Diagrams for Redistricting
  Vincent Cohen-Addad, Philip N. Klein, Neal E. Young
  Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL 2018), 389-396.
• Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
  Amariah Becker, Philip N. Klein, David Saulpic
  26th Annual European Symposium on Algorithms (ESA 2018), 8:1-8:15.

2017

• Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
  Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen
  SIAM Journal on Computing, 46(4): 1280-1303 (2017).
• A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs
  Amariah Becker, Philip N. Klein, David Saulpic
  25th Annual European Symposium on Algorithms (ESA 2017), 12:1-12:15.
• Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs
  Amariah Becker, Eli Fox-Epstein, Philip N. Klein, David Meierfrankenfeld
  16th International Symposium on Experimental Algorithms (2017), 8:1-8:17.

2016

• Local search yields approximation schemes for k-means and k-median in Euclidean and minor-free metrics
  Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu
  Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016), pp. 353-364.
• The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs
  Glencora Borradaile, Philip Klein
  ACM Transactions on Algorithms (TALG 2016).

2015

• On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms
  Philip N. Klein and Neal E. Young
  SIAM Journal on Computing 44(4): 1154-1172 (2015).
• Correlation clustering and two-edge-connected augmentation for planar graphs
  Philip N. Klein, Claire Mathieu, Hang Zhou
  Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015): 554-567.
• A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
  Kyle Fox, Philip N. Klein, Shay Mozes
  Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing (STOC 2015).
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
  Glencora Borradaile, Philip N. Klein, Claire Mathieu
  ACM Transactions on Algorithms (TALG 2015).

2014

• A subexponential parameterized algorithm for Subset TSP on planar graphs
  Philip N. Klein and Dániel Marx
  Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014).
• Approximating k-center in planar graphs
  David Eisenstat, Philip N. Klein, and Claire Mathieu
  Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014).
• Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
  Erik D. Demaine, Mohammadtaghi Hajiaghayi, Philip N. Klein
  ACM Transactions on Algorithms (TALG 2014).

2013

• Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
  David Eisenstat, Philip N. Klein
  Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (STOC 2013).
• Structured recursive separator decompositions for planar graphs in linear time
  Philip N. Klein, Shay Mozes, Christian Sommer
  Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing (STOC 2013).

2012

• A Polynomial-time Approximation Scheme for Planar Multiway Cut
  MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Philip N. Klein, and Claire Mathieu
  Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012).
• An efficient polynomial-time approximation scheme for Steiner forest in planar graphs
  David Eisenstat, Philip N. Klein, and Claire Mathieu
  Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012).
• Solving planar k-terminal cut in O(n^c√k) time
  Philip N. Klein and Dániel Marx
  Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP 2012).

2011

• Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time
  Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen
  Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2011).
• Linear-space approximate distance oracles for planar, bounded-genus, and minor-free graphs
  Ken-ichi Kawarabayashi, Philip N. Klein, and Christian Sommer
  Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011).
• Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter n log n) Time
  Philip N. Klein and Shay Mozes
  Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011).

2010

• Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log² n)-time algorithm
  Philip N. Klein, Shay Mozes, Oren Weimann
  ACM Transactions on Algorithms (TALG 2010).

2009

• Node-weighted Steiner tree and group Steiner tree in planar graphs
  Erik Demaine, MohammadTaghi Hajiaghayi, and Philip N. Klein
  Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009).
• An O(n log n) approximation scheme for Steiner tree in planar graphs
  Glencora Borradaile, Philip Klein, Claire Mathieu
  ACM Transactions on Algorithms (TALG 2009).
• An O(n log n) algorithm for maximum st-flow in a directed planar graph
  Glencora Borradaile, Philip Klein
  Journal of the ACM (JACM 2009).
• Shortest paths in directed planar graphs with negative lengths: a linear-space O(n log^2 n)-time algorithm
  Philip Klein, Shay Mozes, and Oren Weimann
  Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pp. 236-245.

2008

• A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights
  Philip Klein
  SIAM Journal on Computing 37(6) (2008), pp. 1926-1952.
• The two-edge connectivity survivable network problem in planar graphs
  Glencora Borradaile and Philip N. Klein
  Proceedings of the 35th International Conference on Automata, Languages, and Programming (ICALP 2008), pp. 485-501.
• A polynomial-time approximation scheme for Euclidean Steiner forest
  Glencora Borradaile, Philip N. Klein, and Claire Mathieu
  Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pp. 115-124.

2007

• Steiner tree in planar graphs: An O(n log n) approximation scheme with singly-exponential dependence on epsilon
  Glencora Borradaile, Philip N. Klein, and Claire Mathieu
  Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007), pp. 275-286.
• A polynomial-time approximation scheme for Steiner tree in planar graphs
  Glencora Borradaile, Claire Kenyon-Mathieu, and Philip N. Klein
  Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 1285-1294.

2006

• A subset spanner for planar graphs, with application to subset TSP
  Philip N. Klein
  Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing (STOC 2006), pp. 749-756.
• An O(n log n) algorithm for maximum st-flow in a directed planar graph
  Glencora Borradaile and Philip N. Klein
  Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 524-533.

2005

• A linear-time approximation scheme for TSP for planar weighted graphs
  Philip Klein
  Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005), pp. 647-656.
• Multiple-source shortest paths in planar graphs
  Philip Klein
  Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pp. 146-155.

2004

• Approximation through local optimality: designing networks with small degree
  Philip Klein, Radha Krishnan, Balaji Raghavachari, and R. Ravi
  Networks 44 (2004), pp. 203-215.
• Recognition shapes by editing their shock graphs
  Thomas Sebastian, Philip N. Klein, and Benjamin Kimia
  IEEE Transactions on Pattern Analysis and Machine Intelligence 26 (2004), pp. 550-571.

2003

• Detecting race conditions in parallel programs that use semaphores
  Philip N. Klein, Hsueh-I Lu and Robert H.B. Netzer
  Algorithmica 35 (2003) pp. 321-345.
• On aligning curves
  Thomas Sebastian, Philip N. Klein, and Benjamin Kimia
  IEEE Transactions on Pattern Analysis and Machine Intelligence 25 (2003), pp. 116-125.

2002

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

2001

• Recognition shapes by editing shock graphs
  Thomas B. Sebastian, Philip N. Klein, and Benjamin B. Kimia
  Proceedings of the International Conference on Computer Vision (ICCV 2001), pp. 755-762.
• Alignment-based recognition of shape outlines
  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
  Philip N. Klein, Thomas B. Sebastian and Benjamin B. Kimia
  Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 781-790.

2000

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

1999

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

1998

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

1997

• Approximation algorithms for Steiner and directed multicuts
  Philip Klein, Serge Plotkin, Satish Rao, and Éva Tardos
  Journal of Algorithms 22 (1997), pp. 241-269.
• Faster shortest-path algorithms for planar graphs
  Monika Rauch, Philip N. Klein, Satish Rao, and Sairam Subramanian
  Journal of Computer and System Sciences 55 (1997), pp. 3-23.
• A randomized parallel algorithm for single-source shortest paths
  Philip N. Klein and Sairam Subramanian
  Journal of Algorithms 25 (1997), pp. 205-220.

1996

• Efficient parallel algorithms for chordal graphs
  Philip N. Klein
  SIAM Journal on Computing 25 (1996), pp. 797-827.
• Efficient approximation algorithms for semidefinite programs arising from MAX CUT and COLORING
  Philip Klein, Hsueh-I Lu
  Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC 1996), pp. 338-347.
• Finding minimum spanning forests in logarithmic time and linear work using random sampling
  Richard Cole, Philip N. Klein, Robert E. Tarjan
  Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures (SPAA 1996), pp. 243-250.

1995

• A randomized linear-time algorithm to find minimum spanning trees
  David R. Karger, Philip N. Klein, Robert E. Tarjan
  Journal of the ACM (JACM 1995), pp. 321-328.
• A nearly best-possible approximation algorithm for node-weighted Steiner trees
  Philip N. Klein and R. Ravi
  Journal of Algorithms 19 (1995), pp. 104-115.
• When trees collide: An approximation algorithm for the generalized Steiner tree problem on networks
  Ajit Agrawal, Philip N. Klein, and R. Ravi
  SIAM Journal on Computing 24 (1995), pp. 440-456.
• 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.

1994

• Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts
  Philip N. Klein, Serge Plotkin, Clifford Stein, and Éva Tardos
  SIAM Journal on Computing 23 (1994), pp. 466-487.
• A data structure for bicategories, with application to speeding up an approximation algorithm
  Philip N. Klein
  Information Processing Letters 52 (1994), pp. 303-307.
• A linear-work parallel algorithm for finding a minimum spanning tree
  Philip N. Klein, Richard Cole and Robert E. Tarjan
  Proceedings of the 6th ACM Symposium on Parallel Algorithms and Architectures (SPAA 1994), pp. 11-15.

1993

• Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs
  Ming-Yang Kao and Philip N. Klein
  Journal of Computer and System Sciences 47 (1993), pp. 459-500.
• Parallelism, preprocessing, and reachability: a hybrid algorithm for directed graphs
  Philip N. Klein
  Journal of Algorithms 14 (1993), pp. 331-343.
• The lattice structure of flow in planar graphs
  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
  Philip N. Klein and Clifford Stein
  Algorithmica 9 (1993), pp. 23-31.
• A linear-processor, polylog-time algorithm for shortest paths in planar graphs
  Philip N. Klein and Sairam Subramanian
  Proceedings of the 34th Symposium on Foundations of Computer Science (FOCS 1993), pp. 259-270.
• Excluded minors, network decomposition, and multicommodity flow
  Philip N. Klein, Serge Plotkin, and Satish Rao
  Proceedings of the 25th ACM Symposium on Theory of Computing (STOC 1993), pp. 682-690.
• When cycles collapse: a general approximation technique for constrained two-connectivity problems
  Philip N. Klein and R. Ravi
  Proceedings of the 3rd Symposium on Integer Programming and Combinatorial Optimization (IPCO 1993) pp. 39-55.
• On Gazit and Miller's parallel algorithm for planar separators: achieving greater efficiency through random sampling
  Philip N. Klein
  Proceedings of the 5th ACM Symposium on Parallel Algorithms and Architectures (SPAA 1993), pp. 43-49.

1991

• Ordering problems approximated: register sufficiency, single-processor scheduling and interval graph completion
  Ajit Agrawal, Philip N. Klein, and R. Ravi
  Proceedings of the 18th International Conference on Automata, Languages, and Programming (ICALP 1991), pp. 751-762.

1990

• On time-space complexity of reachability queries for preprocessed graphs
  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
  Philip N. Klein and Clifford Stein
  Information Processing Letters 34 (1990), pp. 307-312.

1988

• An efficient parallel algorithm for planarity
  Philip N. Klein and John H. Reif
  Journal of Computer and System Sciences (1988), pp. 190-246.
• Parallel time acceptance of deterministic CFLs on an exclusive-write P-RAM
  Philip N. Klein and John H. Reif
  SIAM Journal on Computing 17 (1988), pp. 463-485.

Book Chapters

• Approximation Algorithms for Optimization Problems
  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, 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, Springer-Verlag (1993), pp. 31-55.
• 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, American Mathematical Society (1993), pp. 371-381.
• Invited review of "Fast approximation algorithms for multicommodity flow problems"
  Philip N. Klein
  Computing Reviews, July 1992.