An Efficient Parallel Algorithm for Planarity. - Philip N. Klein; John H. Reif (J. Comput. Syst. Sci., 1988)

Parallel Time O(log n) Acceptance of Deterministic CFLs on an Exclusive-Write P-RAM. - Philip N. Klein; John H. Reif (SIAM J. Comput., 1988)

Approximation through Multicommodity Flow - Philip N. Klein; Ajit Agrawal; R. Ravi 001; Satish Rao (FOCS, 1990)

Leighton-Rao Might Be Practical: Faster Approximation Algorithms for Concurrent Flow with Uniform Capacities - Philip N. Klein; Clifford Stein 001; Éva Tardos (STOC, 1990)

On the Time-Space Complexity of Reachability Queries for Preprocessed Graphs. - Lisa Hellerstein; Philip N. Klein; Robert Wilber (Inf. Process. Lett., 1990)

A Parallel Algorithm for Eliminating Cycles in Undirected Graphs. - Philip N. Klein; Clifford Stein 001 (Inf. Process. Lett., 1990)

Approximating Concurrent Flow with Unit Demands and Capacities: An Implementation. - James M. Borger; Sarah Kang; Philip N. Klein (Network Flows And Matching, 1991)

Ordering Problems Approximated: Single-Processor Scheduling and Interval Graph Completion. - R. Ravi 001; Ajit Agrawal; Philip N. Klein (ICALP, 1991)

Approximation Through Local Optimality: Designing Networks with Small Degree. - R. Ravi 001; Balaji Raghavachari; Philip N. Klein (FSTTCS, 1992)

A Parallel Randomized Approximation Scheme for Shortest Paths - Philip N. Klein; Sairam Sairam (STOC, 1992)

A linear-processor polylog-time algorithm for shortest paths in planar graphs - Philip N. Klein; Sairam Subramanian (FOCS, 1993)

When cycles collapse: A general approximation technique for constrained two-connectivity problems. - Philip N. Klein; R. Ravi 001 (IPCO, 1993)

On Gazit and Miller's Parallel Algorithm for Planar Separators: Achieving Greater Efficiency Through Random Sampling. - Philip N. Klein (SPAA, 1993)

Excluded minors, network decomposition, and multicommodity flow. - Philip N. Klein; Serge A. Plotkin; Satish Rao (STOC, 1993)

A Fully Dynamic Approximation Scheme for All-Pairs Shortest Paths in Planar Graphs. - Philip N. Klein; Sairam Subramanian (WADS, 1993)

Detecting Race Conditions in Parallel Programs that Use One Semaphore. - Hsueh-I Lu; Philip N. Klein; Robert H. B. Netzer (WADS, 1993)

A Parallel Algorithm for Approximating the Minimum Cycle Cover. - Philip N. Klein; Clifford Stein 001 (Algorithmica, 1993)

Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs. - Philip N. Klein (J. Algorithms, 1993)

Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs. - Ming-Yang Kao; Philip N. Klein (J. Comput. Syst. Sci., 1993)

The Lattice Structure of Flow in Planar Graphs. - Samir Khuller; Joseph Naor; Philip N. Klein (SIAM J. Discret. Math., 1993)

A randomized linear-time algorithm for finding minimum spanning trees. - Philip N. Klein; Robert Endre Tarjan (STOC, 1994)

A Data Structure for Bicategories, with Application to Speeding up an Approximation Algorithm. - Philip N. Klein (Inf. Process. Lett., 1994)

Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts. - Philip N. Klein; Serge A. Plotkin; Clifford Stein 001; Éva Tardos (SIAM J. Comput., 1994)

An Approximate Max-Flow Min-Cut Relation for Unidirected Multicommodity Flow, with Applications. - Philip N. Klein; Satish Rao; Ajit Agrawal; R. Ravi 001 (Comb., 1995)

A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees. - David R. Karger; Philip N. Klein; Robert Endre Tarjan (J. ACM, 1995)

A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees. - Philip N. Klein; R. Ravi 001 (J. Algorithms, 1995)

When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks. - Ajit Agrawal; Philip N. Klein; R. Ravi 001 (SIAM J. Comput., 1995)

Race-Condition Detection in Parallel Computation with Semaphores (Extended Abstract). - Philip N. Klein; Hsueh-I Lu; Robert H. B. Netzer (ESA, 1996)

Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling. - Richard Cole 001; Philip N. Klein; Robert Endre Tarjan (SPAA, 1996)

Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING. - Philip N. Klein; Hsueh-I Lu (STOC, 1996)

Efficient Parallel Algorithms for Chordal Graphs. - Philip N. Klein (SIAM J. Comput., 1996)

Approximation Algorithms for Steiner and Directed Multicuts. - Philip N. Klein; Serge A. Plotkin; Satish Rao; Éva Tardos (J. Algorithms, 1997)

A Randomized Parallel Algorithm for Single-Source Shortest Paths. - Philip N. Klein; Sairam Subramanian (J. Algorithms, 1997)

Faster Shortest-Path Algorithms for Planar Graphs. - Monika Rauch Henzinger; Philip N. Klein; Satish Rao; Sairam Subramanian (J. Comput. Syst. Sci., 1997)

Computing the Edit-Distance between Unrooted Ordered Trees. - Philip N. Klein (ESA, 1998)

Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs. - Philip N. Klein; Hsueh-I Lu (ISAAC, 1998)

A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP. - Sanjeev Arora; Michelangelo Grigni; David R. Karger; Philip N. Klein; Andrzej Woloszyn (SODA, 1998)

A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. - Philip N. Klein; Sairam Subramanian (Algorithmica, 1998)

Approximation Algorithms. - Philip N. Klein; Neal E. Young (Algorithms and Theory of Computation Handbook, 1999)

Using router stamping to identify the source of IP packets. - Thomas W. Doeppner Jr.; Philip N. Klein; Andrew Koyfman (CCS, 2000)

Finding the closest lattice vector when it's unusually close. - Philip N. Klein (SODA, 2000)

A tree-edit-distance algorithm for comparing simple, closed shapes. - Philip N. Klein; Srikanta Tirthapura; Daniel Sharvit; Benjamin B. Kimia (SODA, 2000)

Recognition of Shapes by Editing Shock Graphs. - Thomas B. Sebastian; Philip N. Klein; Benjamin B. Kimia (ICCV, 2001)

Alignment-Based Recognition of Shape Outlines. - Thomas B. Sebastian; Philip N. Klein; Benjamin B. Kimia (IWVF, 2001)

Shape matching using edit-distance: an implementation. - Philip N. Klein; Thomas B. Sebastian; Benjamin B. Kimia (SODA, 2001)

Shock-Based Indexing into Large Shape Databases. - Thomas B. Sebastian; Philip N. Klein; Benjamin B. Kimia (ECCV (3), 2002)

Preprocessing an undirected planar network to enable fast approximate distance queries. - Philip N. Klein (SODA, 2002)

Detecting Race Conditions in Parallel Programs that Use Semaphores. - Philip N. Klein; Robert H. B. Netzer; Hsueh-I Lu (Algorithmica, 2003)

On Aligning Curves. - Thomas B. Sebastian; Philip N. Klein; Benjamin B. Kimia (IEEE Trans. Pattern Anal. Mach. Intell., 2003)

Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. - David R. Karger; Philip N. Klein; Clifford Stein 001; Mikkel Thorup; Neal E. Young (Math. Oper. Res., 2004)

Approximation algorithms for finding low-degree subgraphs. - Philip N. Klein; Radha Krishnan; Balaji Raghavachari; R. Ravi 001 (Networks, 2004)

Recognition of Shapes by Editing Their Shock Graphs. - Thomas B. Sebastian; Philip N. Klein; Benjamin B. Kimia (IEEE Trans. Pattern Anal. Mach. Intell., 2004)

A linear-time approximation scheme for planar weighted TSP. - Philip N. Klein (FOCS, 2005)

Multiple-source shortest paths in planar graphs. - Philip N. Klein (SODA, 2005)

An O (n log n) algorithm for maximum st-flow in a directed planar graph. - Glencora Borradaile; Philip N. Klein (SODA, 2006)

A subset spanner for Planar graphs, : with application to subset TSP. - Philip N. Klein (STOC, 2006)

A polynomial-time approximation scheme for Steiner tree in planar graphs. - Glencora Borradaile; Claire Kenyon-Mathieu; Philip N. Klein (SODA, 2007)

Steiner Tree in Planar Graphs: An O ( n log n ) Approximation Scheme with Singly-Exponential Dependence on Epsilon. - Glencora Borradaile; Philip N. Klein; Claire Mathieu (WADS, 2007)

The Two-Edge Connectivity Survivable Network Problem in Planar Graphs. - Glencora Borradaile; Philip N. Klein (ICALP (1), 2008)

A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights. - Philip N. Klein (SIAM J. Comput., 2008)

An O(n log n) algorithm for maximum st-flow in a directed planar graph. - Glencora Borradaile; Philip N. Klein (J. ACM, 2009)

An O(n log n) approximation scheme for Steiner tree in planar graphs. - Glencora Borradaile; Philip N. Klein; Claire Mathieu (ACM Trans. Algorithms, 2009)

Multiple-source single-sink maximum flow in directed planar graphs in $O(n^{1.5} log n)$ time - Philip N. Klein; Shay Mozes (CoRR, 2010)

Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log2 n)-time algorithm. - Philip N. Klein; Shay Mozes; Oren Weimann (ACM Trans. Algorithms, 2010)

Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs. - Ken-ichi Kawarabayashi; Philip N. Klein; Christian Sommer 001 (ICALP (1), 2011)

Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time. - Philip N. Klein; Shay Mozes (WADS, 2011)

Solving Planar k -Terminal Cut in $O(n^{c sqrt{k}})$ Time. - Philip N. Klein; Dániel Marx (ICALP (1), 2012)

A polynomial-time approximation scheme for planar multiway cut. - MohammadHossein Bateni; MohammadTaghi Hajiaghayi; Philip N. Klein; Claire Mathieu (SODA, 2012)

An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. - David Eisenstat; Philip N. Klein; Claire Mathieu (SODA, 2012)

Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. - David Eisenstat; Philip N. Klein (STOC, 2013)

Structured recursive separator decompositions for planar graphs in linear time. - Philip N. Klein; Shay Mozes; Christian Sommer 001 (STOC, 2013)

Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421). - Glencora Borradaile; Philip N. Klein; Dániel Marx; Claire Mathieu (Dagstuhl Reports, 2013)

A Cryptography Primer: Secrets and Promises - Philip N. Klein (Cambridge University Press, 2014)

Approximating k-center in planar graphs. - David Eisenstat; Philip N. Klein; Claire Mathieu (SODA, 2014)

A subexponential parameterized algorithm for Subset TSP on planar graphs. - Philip N. Klein; Dániel Marx (SODA, 2014)

Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. - Erik D. Demaine; Mohammad Taghi Hajiaghayi; Philip N. Klein (ACM Trans. Algorithms, 2014)

A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection. - Kyle Fox; Philip N. Klein; Shay Mozes (STOC, 2015)

On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms. - Philip N. Klein; Neal E. Young (SIAM J. Comput., 2015)

A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. - Glencora Borradaile; Philip N. Klein; Claire Mathieu (ACM Trans. Algorithms, 2015)

Approximating connectivity domination in weighted bounded-genus graphs. - Vincent Cohen-Addad; Éric Colin de Verdière; Philip N. Klein; Claire Mathieu; David Meierfrankenfeld (STOC, 2016)

The power of local search for clustering. - Vincent Cohen-Addad; Philip N. Klein; Claire Mathieu (CoRR, 2016)

Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221). - Jeff Erickson 001; Philip N. Klein; Dániel Marx; Claire Mathieu (Dagstuhl Reports, 2016)

The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs. - Glencora Borradaile; Philip N. Klein (ACM Trans. Algorithms, 2016)

A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs. - Amariah Becker; Philip N. Klein; David Saulpic (ESA, 2017)

Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs. - Amariah Becker; Eli Fox-Epstein; Philip N. Klein; David Meierfrankenfeld (SEA, 2017)

Polynomial-Time Approximation Schemes for k-Center and Bounded-Capacity Vehicle Routing in Metrics with Bounded Highway Dimension. - Amariah Becker; Philip N. Klein; David Saulpic (CoRR, 2017)

Balanced power diagrams for redistricting. - Vincent Cohen-Addad; Philip N. Klein; Neal E. Young (CoRR, 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 J. Comput., 2017)

Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension. - Amariah Becker; Philip N. Klein; David Saulpic (ESA, 2018)

Balanced centroidal power diagrams for redistricting. - Vincent Cohen-Addad; Philip N. Klein; Neal E. Young (SIGSPATIAL/GIS, 2018)

Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems. - Eli Fox-Epstein; Philip N. Klein; Aaron Schild (SODA, 2019)

A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs. - Amariah Becker; Philip N. Klein; Aaron Schild (WADS, 2019)

A near-linear time minimum Steiner cut algorithm for planar graphs. - Stephen Jue; Philip N. Klein (CoRR, 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 J. Comput., 2019)

On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. - Vincent Cohen-Addad; Arnold Filtser; Philip N. Klein; Hung Le 001 (FOCS, 2020)

The impact of highly compact algorithmic redistricting on the rural-versus-urban balance. - Archer Wheeler; Philip N. Klein (SIGSPATIAL/GIS, 2020)

New hardness results for planar graph problems in p and an algorithm for sparsest cut. - Amir Abboud; Vincent Cohen-Addad; Philip N. Klein (STOC, 2020)

On the computational tractability of a geographic clustering problem arising in redistricting. - Vincent Cohen-Addad; Philip N. Klein; Dániel Marx (CoRR, 2020)

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 (FORC, 2021)

A quasipolynomial (2 + ε)-approximation for planar sparsest cut. - Vincent Cohen-Addad; Anupam Gupta 001; Philip N. Klein; Jason Li 006 (STOC, 2021)

A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut. - Vincent Cohen-Addad; Anupam Gupta 001; Philip N. Klein; Jason Li 006 (CoRR, 2021)

Correlation Clustering and Two-Edge-Connected Augmentation for Planar Graphs. - Philip N. Klein; Claire Mathieu; Hang Zhou 001 (Algorithmica, 2023)