| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | David Eisenstat, Philip N. Klein, Claire Mathieu |
An efficient polynomial-time approximation scheme for Steiner forest in planar graphs.  |
SODA  |
2012 |
DBLP BibTeX RDF |
|
| 1 | MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Philip N. Klein, Claire Mathieu |
A polynomial-time approximation scheme for planar multiway cut. |
SODA |
2012 |
DBLP BibTeX RDF |
|
| 1 | David Eisenstat, Philip N. Klein, Claire Mathieu |
An efficient polynomial-time approximation scheme for Steiner forest in planar graphs |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer |
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Philip N. Klein, Shay Mozes |
Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter*n*log(n)) Time |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen |
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer |
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs. |
ICALP |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Shay Mozes |
Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time. |
WADS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen |
Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Shay Mozes, Oren Weimann |
Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log2 n)-time algorithm. |
ACM Transactions on Algorithms |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Shay Mozes |
Multiple-source single-sink maximum flow in directed planar graphs in $O(n^{1.5} \log n)$ time |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Glencora Borradaile, Philip N. Klein, Claire Mathieu |
An O(n log n) approximation scheme for Steiner tree in planar graphs. |
ACM Transactions on Algorithms |
2009 |
DBLP DOI BibTeX RDF |
planar graphs, Steiner tree, approximation scheme |
| 1 | Glencora Borradaile, Philip N. Klein |
An O(n log n) algorithm for maximum st-flow in a directed planar graph. |
J. ACM |
2009 |
DBLP DOI BibTeX RDF |
planar graphs, Maximum flow |
| 1 | Philip N. Klein, Shay Mozes, Oren Weimann |
Shortest paths in directed planar graphs with negative lengths: a linear-space O(n log2 n)-time algorithm. |
SODA |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Erik D. Demaine, MohammadTaghi Hajiaghayi, Philip N. Klein |
Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. |
ICALP |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein |
A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Glencora Borradaile, Philip N. Klein |
The Two-Edge Connectivity Survivable Network Problem in Planar Graphs. |
ICALP |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Glencora Borradaile, Philip N. Klein, Claire Mathieu |
A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. |
FOCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Glencora Borradaile, Claire Kenyon-Mathieu, Philip N. Klein |
A polynomial-time approximation scheme for Steiner tree in planar graphs. |
SODA |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Glencora Borradaile, Philip N. Klein, Claire Mathieu |
Steiner Tree in Planar Graphs: An O ( n log n ) Approximation Scheme with Singly-Exponential Dependence on Epsilon. |
WADS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Glencora Borradaile, Philip N. Klein |
An O (n log n) algorithm for maximum st-flow in a directed planar graph. |
SODA |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein |
A subset spanner for Planar graphs, : with application to subset TSP. |
STOC |
2006 |
DBLP DOI BibTeX RDF |
traveling salesman problem, planar graph, spanner, approximation scheme |
| 1 | Philip N. Klein |
Multiple-source shortest paths in planar graphs. |
SODA |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein |
A linear-time approximation scheme for planar weighted TSP. |
FOCS |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia |
Recognition of Shapes by Editing Their Shock Graphs. |
IEEE Trans. Pattern Anal. Mach. Intell. |
2004 |
DBLP DOI BibTeX RDF |
dynamic programming, object recognition, graph matching, edit distance, shape matching, shock graphs, Shape deformation |
| 1 | Philip N. Klein, Radha Krishnan, Balaji Raghavachari, R. Ravi |
Approximation algorithms for finding low-degree subgraphs. |
Networks |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young |
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. |
Math. Oper. Res. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia |
On Aligning Curves. |
IEEE Trans. Pattern Anal. Mach. Intell. |
2003 |
DBLP DOI BibTeX RDF |
Curve alignment, dynamic programming, prototypes, recognition, correspondence |
| 1 | Philip N. Klein, Robert H. B. Netzer, Hsueh-I Lu |
Detecting Race Conditions in Parallel Programs that Use Semaphores. |
Algorithmica |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Neal E. Young |
On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms |
CoRR |
2002 |
DBLP BibTeX RDF |
|
| 1 | David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young |
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut |
CoRR |
2002 |
DBLP BibTeX RDF |
|
| 1 | Philip N. Klein, Hsueh-I Lu, Robert H. B. Netzer |
Detecting Race Conditions in Parallel Programs that Use Semaphores |
CoRR |
2002 |
DBLP BibTeX RDF |
|
| 1 | Philip N. Klein |
Preprocessing an undirected planar network to enable fast approximate distance queries. |
SODA |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia |
Shock-Based Indexing into Large Shape Databases. |
ECCV |
2002 |
DBLP DOI BibTeX RDF |
exemplars, object recognition, categorization, shape matching, shape retrieval, Similarity metric |
| 1 | Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia |
Alignment-Based Recognition of Shape Outlines. |
IWVF |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Thomas B. Sebastian, Benjamin B. Kimia |
Shape matching using edit-distance: an implementation. |
SODA |
2001 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia |
Recognition of Shapes by Editing Shock Graphs. |
ICCV |
2001 |
DBLP BibTeX RDF |
|
| 1 | Philip N. Klein, Srikanta Tirthapura, Daniel Sharvit, Benjamin B. Kimia |
A tree-edit-distance algorithm for comparing simple, closed shapes. |
SODA |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein |
Finding the closest lattice vector when it's unusually close. |
SODA |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Thomas W. Doeppner, Philip N. Klein, Andrew Koyfman |
Using router stamping to identify the source of IP packets. |
ACM Conference on Computer and Communications Security |
2000 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Neal E. Young |
On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms. |
IPCO |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young |
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. |
STOC |
1999 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Sairam Subramanian |
A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. |
Algorithmica |
1998 |
DBLP DOI BibTeX RDF |
Minimum-cost path, Minimum-cost path, Shortest path, Shortest path, Graph algorithm, Graph algorithm, Planar graph, Planar graph, Key words, Dynamic algorithm, Dynamic algorithm |
| 1 | Philip N. Klein |
Computing the Edit-Distance between Unrooted Ordered Trees. |
ESA |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, Andrzej Woloszyn |
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP. |
SODA |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Hsueh-I Lu |
Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs. |
ISAAC |
1998 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Sairam Subramanian |
A Randomized Parallel Algorithm for Single-Source Shortest Paths. |
J. Algorithms |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Serge A. Plotkin, Satish Rao, Éva Tardos |
Approximation Algorithms for Steiner and Directed Multicuts. |
J. Algorithms |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Monika Rauch Henzinger, Philip N. Klein, Satish Rao, Sairam Subramanian |
Faster Shortest-Path Algorithms for Planar Graphs. |
J. Comput. Syst. Sci. |
1997 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein |
Efficient Parallel Algorithms for Chordal Graphs. |
SIAM J. Comput. |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Hsueh-I Lu, Robert H. B. Netzer |
Race-Condition Detection in Parallel Computation with Semaphores (Extended Abstract). |
ESA |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Richard Cole, Philip N. Klein, Robert Endre Tarjan |
Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling. |
SPAA |
1996 |
DBLP BibTeX RDF |
|
| 1 | Philip N. Klein, Hsueh-I Lu |
Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING. |
STOC |
1996 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, R. Ravi |
A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees. |
J. Algorithms |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | David R. Karger, Philip N. Klein, Robert Endre Tarjan |
A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees. |
J. ACM |
1995 |
DBLP DOI BibTeX RDF |
randomized algorithm, minimum spanning tree, matroid |
| 1 | Philip N. Klein, Satish Rao, Ajit Agrawal, R. Ravi |
An Approximate Max-Flow Min-Cut Relation for Unidirected Multicommodity Flow, with Applications. |
Combinatorica |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Ajit Agrawal, Philip N. Klein, R. Ravi |
When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks. |
SIAM J. Comput. |
1995 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein |
A Data Structure for Bicategories, with Application to Speeding up an Approximation Algorithm. |
Inf. Process. Lett. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Serge A. Plotkin, Clifford Stein, Éva Tardos |
Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts. |
SIAM J. Comput. |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Satish Rao, Monika Rauch Henzinger, Sairam Subramanian |
Faster shortest-path algorithms for planar graphs. |
STOC |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Robert Endre Tarjan |
A randomized linear-time algorithm for finding minimum spanning trees. |
STOC |
1994 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Clifford Stein |
A Parallel Algorithm for Approximating the Minimum Cycle Cover. |
Algorithmica |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein |
Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs. |
J. Algorithms |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Samir Khuller, Joseph Naor, Philip N. Klein |
The Lattice Structure of Flow in Planar Graphs. |
SIAM J. Discrete Math. |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Ming-Yang Kao, Philip N. Klein |
Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs. |
J. Comput. Syst. Sci. |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Hsueh-I Lu, Philip N. Klein, Robert H. B. Netzer |
Detecting Race Conditions in Parallel Programs that Use One Semaphore. |
WADS |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Sairam Subramanian |
A Fully Dynamic Approximation Scheme for All-Pairs Shortest Paths in Planar Graphs. |
WADS |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein |
On Gazit and Miller's Parallel Algorithm for Planar Separators: Achieving Greater Efficiency Through Random Sampling. |
SPAA |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, R. Ravi |
A nearly best-possible approximation algorithm for node-weighted Steiner trees. |
IPCO |
1993 |
DBLP BibTeX RDF |
|
| 1 | Philip N. Klein, R. Ravi |
When cycles collapse: A general approximation technique for constrained two-connectivity problems. |
IPCO |
1993 |
DBLP BibTeX RDF |
|
| 1 | Philip N. Klein, Sairam Subramanian |
A linear-processor polylog-time algorithm for shortest paths in planar graphs |
FOCS |
1993 |
DBLP DOI BibTeX RDF |
linear-processor polylog-time algorithm, directed planar graphs, bounded-genus graphs, 2-dimensional overlap graphs, shortest paths, planar graphs, separators, decomposition tree |
| 1 | Philip N. Klein, Serge A. Plotkin, Satish Rao |
Excluded minors, network decomposition, and multicommodity flow. |
STOC |
1993 |
DBLP DOI BibTeX RDF |
|
| 1 | R. Ravi, Balaji Raghavachari, Philip N. Klein |
Approximation Through Local Optimality: Designing Networks with Small Degree. |
FSTTCS |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Sairam Sairam |
A Parallel Randomized Approximation Scheme for Shortest Paths |
STOC |
1992 |
DBLP DOI BibTeX RDF |
|
| 1 | R. Ravi, Ajit Agrawal, Philip N. Klein |
Ordering Problems Approximated: Single-Processor Scheduling and Interval Graph Completion. |
ICALP |
1991 |
DBLP DOI BibTeX RDF |
|
| 1 | Ajit Agrawal, Philip N. Klein, R. Ravi |
When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks |
STOC |
1991 |
DBLP DOI BibTeX RDF |
|
| 1 | Lisa Hellerstein, Philip N. Klein, Robert Wilber |
On the Time-Space Complexity of Reachability Queries for Preprocessed Graphs. |
Inf. Process. Lett. |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Clifford Stein |
A Parallel Algorithm for Eliminating Cycles in Undirected Graphs. |
Inf. Process. Lett. |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Ajit Agrawal, R. Ravi, Satish Rao |
Approximation through Multicommodity Flow |
FOCS |
1990 |
DBLP DOI BibTeX RDF |
minimum deletion, max-flow-min-cut theorem, approximation algorithms, multicommodity flow |
| 1 | Ming-Yang Kao, Philip N. Klein |
Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs |
STOC |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, Clifford Stein, Éva Tardos |
Leighton-Rao Might Be Practical: Faster Approximation Algorithms for Concurrent Flow with Uniform Capacities |
STOC |
1990 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, John H. Reif |
An Efficient Parallel Algorithm for Planarity. |
J. Comput. Syst. Sci. |
1988 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein, John H. Reif |
Parallel Time O(log n) Acceptance of Deterministic CFLs on an Exclusive-Write P-RAM. |
SIAM J. Comput. |
1988 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein |
Efficient Parallel Algorithms for Chordal Graphs |
FOCS |
1988 |
DBLP DOI BibTeX RDF |
elimination ordering, optimal coloring, breadth-first search tree, depth-first search tree, parallel algorithms, interval graphs, chordal graphs, isomorphism, maximum independent set, maximum clique |
| 1 | Philip N. Klein, John H. Reif |
An Efficient Parallel Algorithm for Planarity |
FOCS |
1986 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")