| 2021 | STOC | A quasipolynomial (2 + | Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li |
| 2020 | FOCS | On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. | Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le |
| 2020 | STOC | New hardness results for planar graph problems in p and an algorithm for sparsest cut. | Amir Abboud, Vincent Cohen-Addad, Philip N. Klein |
| 2019 | SODA | Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems. | Eli Fox-Epstein, Philip N. Klein, Aaron Schild |
| 2019 | WADS | A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs. | Amariah Becker, Philip N. Klein, Aaron Schild |
| 2018 | ESA | Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension. | Amariah Becker, Philip N. Klein, David Saulpic |
| 2017 | ESA | A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs. | Amariah Becker, Philip N. Klein, David Saulpic |
| 2016 | FOCS | 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 |
| 2016 | STOC | Approximating connectivity domination in weighted bounded-genus graphs. | Vincent Cohen-Addad, ric Colin de Verdire, Philip N. Klein, Claire Mathieu, David Meierfrankenfeld |
| 2015 | STOC | A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection. | Kyle Fox, Philip N. Klein, Shay Mozes |
| 2015 | STACS | Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs. | Philip N. Klein, Claire Mathieu, Hang Zhou |
| 2014 | SODA | Approximating | David Eisenstat, Philip N. Klein, Claire Mathieu |
| 2014 | SODA | A subexponential parameterized algorithm for Subset TSP on planar graphs. | Philip N. Klein, Dniel Marx |
| 2013 | STOC | Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. | David Eisenstat, Philip N. Klein |
| 2013 | STOC | Structured recursive separator decompositions for planar graphs in linear time. | Philip N. Klein, Shay Mozes, Christian Sommer |
| 2012 | ICALP | Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time. | Philip N. Klein, Dniel Marx |
| 2012 | SODA | A polynomial-time approximation scheme for planar multiway cut. | MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Philip N. Klein, Claire Mathieu |
| 2012 | SODA | An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. | David Eisenstat, Philip N. Klein, Claire Mathieu |
| 2011 | FOCS | 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 |
| 2011 | ICALP | Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs. | Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer |
| 2011 | WADS | Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time. | Philip N. Klein, Shay Mozes |
| 2009 | ICALP | Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. | Erik D. Demaine, MohammadTaghi Hajiaghayi, Philip N. Klein |
| 2009 | SODA | Shortest paths in directed planar graphs with negative lengths: a linear-space | Philip N. Klein, Shay Mozes, Oren Weimann |
| 2008 | FOCS | A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. | Glencora Borradaile, Philip N. Klein, Claire Mathieu |
| 2008 | ICALP | The Two-Edge Connectivity Survivable Network Problem in Planar Graphs. | Glencora Borradaile, Philip N. Klein |
| 2007 | SODA | A polynomial-time approximation scheme for Steiner tree in planar graphs. | Glencora Borradaile, Claire Kenyon-Mathieu, Philip N. Klein |
| 2007 | WADS | Steiner Tree in Planar Graphs: An | Glencora Borradaile, Philip N. Klein, Claire Mathieu |
| 2006 | SODA | An | Glencora Borradaile, Philip N. Klein |
| 2006 | STOC | A subset spanner for Planar graphs, : with application to subset TSP. | Philip N. Klein |
| 2005 | FOCS | A linear-time approximation scheme for planar weighted TSP. | Philip N. Klein |
| 2005 | SODA | Multiple-source shortest paths in planar graphs. | Philip N. Klein |
| 2002 | ECCV | Shock-Based Indexing into Large Shape Databases. | Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia |
| 2002 | SODA | Preprocessing an undirected planar network to enable fast approximate distance queries. | Philip N. Klein |
| 2001 | ICCV | Recognition of Shapes by Editing Shock Graphs. | Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia |
| 2001 | SODA | Shape matching using edit-distance: an implementation. | Philip N. Klein, Thomas B. Sebastian, Benjamin B. Kimia |
| 2000 | CCS | Using router stamping to identify the source of IP packets. | Thomas W. Doeppner Jr., Philip N. Klein, Andrew Koyfman |
| 2000 | SODA | Finding the closest lattice vector when it's unusually close. | Philip N. Klein |
| 2000 | SODA | A tree-edit-distance algorithm for comparing simple, closed shapes. | Philip N. Klein, Srikanta Tirthapura, Daniel Sharvit, Benjamin B. Kimia |
| 1999 | IPCO | On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms. | Philip N. Klein, Neal E. Young |
| 1999 | STOC | Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. | David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young |
| 1998 | ESA | Computing the Edit-Distance between Unrooted Ordered Trees. | Philip N. Klein |
| 1998 | ISAAC | Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs. | Philip N. Klein, Hsueh-I Lu |
| 1998 | SODA | A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP. | Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, Andrzej Woloszyn |
| 1996 | ESA | Race-Condition Detection in Parallel Computation with Semaphores (Extended Abstract). | Philip N. Klein, Hsueh-I Lu, Robert H. B. Netzer |
| 1996 | STOC | Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING. | Philip N. Klein, Hsueh-I Lu |
| 1996 | SPAA | Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling. | Richard Cole, Philip N. Klein, Robert Endre Tarjan |
| 1994 | STOC | Faster shortest-path algorithms for planar graphs. | Philip N. Klein, Satish Rao, Monika Rauch, Sairam Subramanian |
| 1994 | STOC | A randomized linear-time algorithm for finding minimum spanning trees. | Philip N. Klein, Robert Endre Tarjan |
| 1993 | FOCS | A linear-processor polylog-time algorithm for shortest paths in planar graphs | Philip N. Klein, Sairam Subramanian |
| 1993 | IPCO | When cycles collapse: A general approximation technique for constrained two-connectivity problems. | Philip N. Klein, R. Ravi |
| 1993 | IPCO | A nearly best-possible approximation algorithm for node-weighted Steiner trees. | Philip N. Klein, R. Ravi |
| 1993 | STOC | Excluded minors, network decomposition, and multicommodity flow. | Philip N. Klein, Serge A. Plotkin, Satish Rao |
| 1993 | SPAA | On Gazit and Miller's Parallel Algorithm for Planar Separators: Achieving Greater Efficiency Through Random Sampling. | Philip N. Klein |
| 1993 | WADS | A Fully Dynamic Approximation Scheme for All-Pairs Shortest Paths in Planar Graphs. | Philip N. Klein, Sairam Subramanian |
| 1993 | WADS | Detecting Race Conditions in Parallel Programs that Use One Semaphore. | Hsueh-I Lu, Philip N. Klein, Robert H. B. Netzer |
| 1992 | STOC | A Parallel Randomized Approximation Scheme for Shortest Paths | Philip N. Klein, Sairam Sairam |
| 1991 | ICALP | Ordering Problems Approximated: Single-Processor Scheduling and Interval Graph Completion. | R. Ravi, Ajit Agrawal, Philip N. Klein |
| 1991 | STOC | When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks | Ajit Agrawal, Philip N. Klein, R. Ravi |
| 1990 | FOCS | Approximation through Multicommodity Flow | Philip N. Klein, Ajit Agrawal, R. Ravi, Satish Rao |
| 1990 | STOC | Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs | Ming-Yang Kao, Philip N. Klein |
| 1990 | STOC | Leighton-Rao Might Be Practical: Faster Approximation Algorithms for Concurrent Flow with Uniform Capacities | Philip N. Klein, Clifford Stein, va Tardos |
| 1988 | FOCS | Efficient Parallel Algorithms for Chordal Graphs | Philip N. Klein |
| 1986 | FOCS | An Efficient Parallel Algorithm for Planarity | Philip N. Klein, John H. Reif |