P. Klein

Most-cited papers

Recognition of shapes by editing their shock graphs
Thomas B. Sebastian, P. Klein, B. Kimia
2004IEEE Transactions on Pattern Analysis and Machine Intelligence785 citations Open access
Semantic Scholar
On Aligning Curves
Thomas B. Sebastian, P. Klein, B. Kimia
2003IEEE Transactions on Pattern Analysis and Machine Intelligence413 citations
Semantic Scholar
Recognition of Shapes by Editing Shock Graphs
Thomas B. Sebastian, P. Klein, B. Kimia
2001IEEE International Conference on Computer Vision314 citations
Semantic Scholar
Computing the Edit-Distance between Unrooted Ordered Trees
P. Klein
1998Embedded Systems and Applications291 citations
Semantic Scholar
Finding the closest lattice vector when it's unusually close
P. Klein
2000ACM-SIAM Symposium on Discrete Algorithms228 citations
Semantic Scholar
Multiple-source shortest paths in planar graphs
P. Klein
2005ACM-SIAM Symposium on Discrete Algorithms194 citations
Semantic Scholar
Rounding algorithms for a geometric embedding of minimum multiway cut
David R Karger, P. Klein, Cliff Stein, M. Thorup +1 more
1999Symposium on the Theory of Computing171 citations Open access
Semantic Scholar
A polynomial-time approximation scheme for weighted planar graph TSP
Sanjeev Arora, Michelangelo Grigni, David R Karger, P. Klein +1 more
1998ACM-SIAM Symposium on Discrete Algorithms146 citations
Semantic Scholar
Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics
Vincent Cohen-Addad, P. Klein, Claire Mathieu
2016IEEE Annual Symposium on Foundations of Computer Science144 citations Open access
Semantic Scholar
A Randomized Parallel Algorithm for Single-Source Shortest Paths
P. Klein, Sairam Subramanian
1997J. Algorithms119 citations
Semantic Scholar
Shock-Based Indexing into Large Shape Databases
Thomas B. Sebastian, P. Klein, B. Kimia
2002European Conference on Computer Vision117 citations Open access
Semantic Scholar
An O(n log n) approximation scheme for Steiner tree in planar graphs
G. Borradaile, P. Klein, Claire Mathieu
2009TALG113 citations
Semantic Scholar
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time
G. Borradaile, P. Klein, S. Mozes, Yahav Nussbaum +1 more
2011IEEE Annual Symposium on Foundations of Computer Science109 citations Open access
Semantic Scholar
A tree-edit-distance algorithm for comparing simple, closed shapes
P. Klein, S. Tirthapura, D. Sharvit, B. Kimia
2000ACM-SIAM Symposium on Discrete Algorithms107 citations
Semantic Scholar
Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log2 n)-time algorithm
P. Klein, S. Mozes, Oren Weimann
2009TALG104 citations
Semantic Scholar
An O (n log n) algorithm for maximum st-flow in a directed planar graph
G. Borradaile, P. Klein
2006ACM-SIAM Symposium on Discrete Algorithms102 citations
Semantic Scholar
Structured recursive separator decompositions for planar graphs in linear time
P. Klein, S. Mozes, Christian Sommer
2012Symposium on the Theory of Computing91 citations Open access
Semantic Scholar
Using router stamping to identify the source of IP packets
Thomas W. Doeppner, P. Klein, Andrew Koyfman
2000Conference on Computer and Communications Security85 citations
Semantic Scholar
A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
P. Klein
2008SIAM journal on computing (Print)84 citations Open access
Semantic Scholar
Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
E. Demaine, Mohammadtaghi Hajiaghayi, P. Klein
2009TALG83 citations Open access
Semantic Scholar
Approximation Algorithms for Steiner and Directed Multicuts
P. Klein, S. Plotkin, Satish B. Rao, É. Tardos
1997J. Algorithms83 citations Open access
Semantic Scholar
Preprocessing an undirected planar network to enable fast approximate distance queries
P. Klein
2002ACM-SIAM Symposium on Discrete Algorithms82 citations
Semantic Scholar
A subset spanner for Planar graphs, with application to subset TSP
P. Klein
2006Symposium on the Theory of Computing81 citations
Semantic Scholar
A polynomial-time approximation scheme for Steiner tree in planar graphs
G. Borradaile, C. Kenyon-Mathieu, P. Klein
2007ACM-SIAM Symposium on Discrete Algorithms74 citations
Semantic Scholar
A linear-time approximation scheme for planar weighted TSP
P. Klein
2005IEEE Annual Symposium on Foundations of Computer Science72 citations
Semantic Scholar
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs
K. Kawarabayashi, P. Klein, Christian Sommer
2011International Colloquium on Automata, Languages and Programming69 citations Open access
Semantic Scholar
Shape matching using edit-distance: an implementation
P. Klein, Thomas B. Sebastian, B. Kimia
2001ACM-SIAM Symposium on Discrete Algorithms69 citations
Semantic Scholar
Faster Shortest-Path Algorithms for Planar Graphs
M. Henzinger, P. Klein, Satish B. Rao, Sairam Subramanian
1997Journal of computer and system sciences (Print)69 citations Open access
Semantic Scholar
On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms
P. Klein, N. Young
1999SIAM journal on computing (Print)63 citations Open access
Semantic Scholar
Shortest Paths in Directed Planar Graphs with Negative Lengths : a Linear-Space O ( n log 2 n )-Time Algorithm
P. Klein, S. Mozes, Oren Weimann
200861 citations
Semantic Scholar
A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs
P. Klein, Sairam Subramanian
1998Algorithmica61 citations Open access
Semantic Scholar
Indexing based on edit-distance matching of shape graphs
S. Tirthapura, D. Sharvit, P. Klein, B. Kimia
1998Other Conferences58 citations
Semantic Scholar
A subexponential parameterized algorithm for Subset TSP on planar graphs
P. Klein, Dániel Marx
2014ACM-SIAM Symposium on Discrete Algorithms57 citations
Semantic Scholar
An O(n log n) algorithm for maximum st-flow in a directed planar graph
G. Borradaile, P. Klein
2009JACM47 citations
Semantic Scholar
Alignment-Based Recognition of Shape Outlines
Thomas B. Sebastian, P. Klein, B. Kimia
2001International Workshop on Visual Form47 citations
Semantic Scholar
Identifying and Bounding Ethnic Neighborhoods
J. Logan, S. Spielman, Hong-Wei Xu, P. Klein
2011Urban Geography45 citations Open access
Semantic Scholar
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
Vincent Cohen-Addad, Arnold Filtser, P. Klein, Hung Le
2020IEEE Annual Symposium on Foundations of Computer Science44 citations Open access
Semantic Scholar
A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
G. Borradaile, P. Klein, Claire Mathieu
20082008 49th Annual IEEE Symposium on Foundations of Computer Science41 citations Open access
Semantic Scholar
Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension
Amariah Becker, P. Klein, David Saulpic
2018Embedded Systems and Applications36 citations
Semantic Scholar
Balanced centroidal power diagrams for redistricting
Vincent Cohen-Addad, P. Klein, N. Young
2018SIGSPATIAL/GIS36 citations
Semantic Scholar
Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs
David Eisenstat, P. Klein
2013Symposium on the Theory of Computing36 citations
Semantic Scholar
An efficient polynomial-time approximation scheme for Steiner forest in planar graphs
David Eisenstat, P. Klein, Claire Mathieu
2011ACM-SIAM Symposium on Discrete Algorithms35 citations
Semantic Scholar
Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems
Eli Fox-Epstein, P. Klein, Aaron Schild
2019ACM-SIAM Symposium on Discrete Algorithms34 citations
Semantic Scholar
Steiner Tree in Planar Graphs: An O ( n log n ) Approximation Scheme with Singly-Exponential Dependence on Epsilon
G. Borradaile, P. Klein, Claire Mathieu
2007Workshop on Algorithms and Data Structures33 citations
Semantic Scholar
Approximating k-center in planar graphs
David Eisenstat, P. Klein, Claire Mathieu
2014ACM-SIAM Symposium on Discrete Algorithms31 citations
Semantic Scholar
A polynomial-time approximation scheme for planar multiway cut
M. Bateni, M. Hajiaghayi, P. Klein, Claire Mathieu
2012ACM-SIAM Symposium on Discrete Algorithms25 citations
Semantic Scholar
A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs
Amariah Becker, P. Klein, Aaron Schild
2019Workshop on Algorithms and Data Structures24 citations Open access
Semantic Scholar
A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs
Amariah Becker, P. Klein, David Saulpic
2017Embedded Systems and Applications24 citations
Semantic Scholar
Approximation algorithms for NP-hard optimization problems
P. Klein, N. Young
201024 citations
Semantic Scholar
Approximation algorithms for finding low‐degree subgraphs
P. Klein, R. Krishnan, Balaji Raghavachari, R. Ravi
2004Networks22 citations
Semantic Scholar