 | 2009 |
|---|
| 74 |       | Erik D. Demaine,
MohammadTaghi Hajiaghayi,
Philip N. Klein:
Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs.
ICALP (1) 2009: 328-340 |
| 73 | | 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: 236-245 |
| 72 | | Glencora Borradaile,
Philip N. Klein,
Claire Mathieu:
An O(n log n) approximation scheme for Steiner tree in planar graphs.
ACM Transactions on Algorithms 5(3): (2009) |
| 71 | | Glencora Borradaile,
Philip N. Klein:
An O(n log n) algorithm for maximum st-flow in a directed planar graph.
J. ACM 56(2): (2009) |
| 2008 |
|---|
| 70 | | Glencora Borradaile,
Philip N. Klein,
Claire Mathieu:
A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest.
FOCS 2008: 115-124 |
| 69 | | Glencora Borradaile,
Philip N. Klein:
The Two-Edge Connectivity Survivable Network Problem in Planar Graphs.
ICALP (1) 2008: 485-501 |
| 68 | | Philip N. Klein:
A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights.
SIAM J. Comput. 37(6): 1926-1952 (2008) |
| 2007 |
|---|
| 67 | | Glencora Borradaile,
Claire Kenyon-Mathieu,
Philip N. Klein:
A polynomial-time approximation scheme for Steiner tree in planar graphs.
SODA 2007: 1285-1294 |
| 66 | | 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: 275-286 |
| 2006 |
|---|
| 65 | | Glencora Borradaile,
Philip N. Klein:
An O (n log n) algorithm for maximum st-flow in a directed planar graph.
SODA 2006: 524-533 |
| 64 | | Philip N. Klein:
A subset spanner for Planar graphs, : with application to subset TSP.
STOC 2006: 749-756 |
| 2005 |
|---|
| 63 | | Philip N. Klein:
A linear-time approximation scheme for planar weighted TSP.
FOCS 2005: 647-657 |
| 62 | | Philip N. Klein:
Multiple-source shortest paths in planar graphs.
SODA 2005: 146-155 |
| 2004 |
|---|
| 61 | | Thomas B. Sebastian,
Philip N. Klein,
Benjamin B. Kimia:
Recognition of Shapes by Editing Their Shock Graphs.
IEEE Trans. Pattern Anal. Mach. Intell. 26(5): 550-571 (2004) |
| 60 | | 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. 29(3): 436-461 (2004) |
| 59 | | Philip N. Klein,
Radha Krishnan,
Balaji Raghavachari,
R. Ravi:
Approximation algorithms for finding low-degree subgraphs.
Networks 44(3): 203-215 (2004) |
| 2003 |
|---|
| 58 | | Philip N. Klein,
Robert H. B. Netzer,
Hsueh-I Lu:
Detecting Race Conditions in Parallel Programs that Use Semaphores.
Algorithmica 35(4): 321-345 (2003) |
| 57 | | Thomas B. Sebastian,
Philip N. Klein,
Benjamin B. Kimia:
On Aligning Curves.
IEEE Trans. Pattern Anal. Mach. Intell. 25(1): 116-125 (2003) |
| 2002 |
|---|
| 56 | | Thomas B. Sebastian,
Philip N. Klein,
Benjamin B. Kimia:
Shock-Based Indexing into Large Shape Databases.
ECCV (3) 2002: 731-746 |
| 55 | | Philip N. Klein:
Preprocessing an undirected planar network to enable fast approximate distance queries.
SODA 2002: 820-827 |
| 54 | | Philip N. Klein,
Neal E. Young:
On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms
CoRR cs.DS/0205046: (2002) |
| 53 | | David R. Karger,
Philip N. Klein,
Clifford Stein,
Mikkel Thorup,
Neal E. Young:
Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut
CoRR cs.DS/0205051: (2002) |
| 52 | | Philip N. Klein,
Hsueh-I Lu,
Robert H. B. Netzer:
Detecting Race Conditions in Parallel Programs that Use Semaphores
CoRR cs.DS/0208004: (2002) |
| 2001 |
|---|
| 51 |  | Thomas B. Sebastian,
Philip N. Klein,
Benjamin B. Kimia:
Recognition of Shapes by Editing Shock Graphs.
ICCV 2001: 755-762 |
| 50 | | Thomas B. Sebastian,
Philip N. Klein,
Benjamin B. Kimia:
Alignment-Based Recognition of Shape Outlines.
IWVF 2001: 606-618 |
| 49 | | Philip N. Klein,
Thomas B. Sebastian,
Benjamin B. Kimia:
Shape matching using edit-distance: an implementation.
SODA 2001: 781-790 |
| 2000 |
|---|
| 48 | | 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: 184-189 |
| 47 | | Philip N. Klein,
Srikanta Tirthapura,
Daniel Sharvit,
Benjamin B. Kimia:
A tree-edit-distance algorithm for comparing simple, closed shapes.
SODA 2000: 696-704 |
| 46 | | Philip N. Klein:
Finding the closest lattice vector when it's unusually close.
SODA 2000: 937-941 |
| 1999 |
|---|
| 45 | | Philip N. Klein,
Neal E. Young:
On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms.
IPCO 1999: 320-327 |
| 44 | | 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: 668-678 |
| 1998 |
|---|
| 43 | | Philip N. Klein:
Computing the Edit-Distance between Unrooted Ordered Trees.
ESA 1998: 91-102 |
| 42 | | Philip N. Klein,
Hsueh-I Lu:
Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs.
ISAAC 1998: 387-396 |
| 41 | | Sanjeev Arora,
Michelangelo Grigni,
David R. Karger,
Philip N. Klein,
Andrzej Woloszyn:
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP.
SODA 1998: 33-41 |
| 40 | | Philip N. Klein,
Sairam Subramanian:
A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs.
Algorithmica 22(3): 235-249 (1998) |
| 1997 |
|---|
| 39 | | Philip N. Klein,
Serge A. Plotkin,
Satish Rao,
Éva Tardos:
Approximation Algorithms for Steiner and Directed Multicuts.
J. Algorithms 22(2): 241-269 (1997) |
| 38 | | Philip N. Klein,
Sairam Subramanian:
A Randomized Parallel Algorithm for Single-Source Shortest Paths.
J. Algorithms 25(2): 205-220 (1997) |
| 37 | | Monika Rauch Henzinger,
Philip N. Klein,
Satish Rao,
Sairam Subramanian:
Faster Shortest-Path Algorithms for Planar Graphs.
J. Comput. Syst. Sci. 55(1): 3-23 (1997) |
| 1996 |
|---|
| 36 | | Philip N. Klein,
Hsueh-I Lu,
Robert H. B. Netzer:
Race-Condition Detection in Parallel Computation with Semaphores (Extended Abstract).
ESA 1996: 445-459 |
| 35 | | Richard Cole,
Philip N. Klein,
Robert Endre Tarjan:
Finding Minimum Spanning Forests in Logarithmic Time and Linear Work Using Random Sampling.
SPAA 1996: 243-250 |
| 34 | | Philip N. Klein,
Hsueh-I Lu:
Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING.
STOC 1996: 338-347 |
| 33 | | Philip N. Klein:
Efficient Parallel Algorithms for Chordal Graphs.
SIAM J. Comput. 25(4): 797-827 (1996) |
| 1995 |
|---|
| 32 | | Philip N. Klein,
Satish Rao,
Ajit Agrawal,
R. Ravi:
An Approximate Max-Flow Min-Cut Relation for Unidirected Multicommodity Flow, with Applications.
Combinatorica 15(2): 187-202 (1995) |
| 31 | | David R. Karger,
Philip N. Klein,
Robert Endre Tarjan:
A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees.
J. ACM 42(2): 321-328 (1995) |
| 30 | | Philip N. Klein,
R. Ravi:
A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees.
J. Algorithms 19(1): 104-115 (1995) |
| 29 | | Ajit Agrawal,
Philip N. Klein,
R. Ravi:
When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks.
SIAM J. Comput. 24(3): 440-456 (1995) |
| 1994 |
|---|
| 28 | | Philip N. Klein,
Satish Rao,
Monika Rauch Henzinger,
Sairam Subramanian:
Faster shortest-path algorithms for planar graphs.
STOC 1994: 27-37 |
| 27 | | Philip N. Klein,
Robert Endre Tarjan:
A randomized linear-time algorithm for finding minimum spanning trees.
STOC 1994: 9-15 |
| 26 | | Philip N. Klein:
A Data Structure for Bicategories, with Application to Speeding up an Approximation Algorithm.
Inf. Process. Lett. 52(6): 303-307 (1994) |
| 25 | | 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. 23(3): 466-487 (1994) |
| 1993 |
|---|
| 24 | | Philip N. Klein,
Sairam Subramanian:
A linear-processor polylog-time algorithm for shortest paths in planar graphs
FOCS 1993: 259-270 |
| 23 | | Philip N. Klein,
R. Ravi:
A nearly best-possible approximation algorithm for node-weighted Steiner trees.
IPCO 1993: 323-332 |
| 22 | | Philip N. Klein,
R. Ravi:
When cycles collapse: A general approximation technique for constrained two-connectivity problems.
IPCO 1993: 39-55 |
| 21 | | Philip N. Klein:
On Gazit and Miller's Parallel Algorithm for Planar Separators: Achieving Greater Efficiency Through Random Sampling.
SPAA 1993: 43-49 |
| 20 | | Philip N. Klein,
Serge A. Plotkin,
Satish Rao:
Excluded minors, network decomposition, and multicommodity flow.
STOC 1993: 682-690 |
| 19 | | Philip N. Klein,
Sairam Subramanian:
A Fully Dynamic Approximation Scheme for All-Pairs Shortest Paths in Planar Graphs.
WADS 1993: 442-451 |
| 18 | | Hsueh-I Lu,
Philip N. Klein,
Robert H. B. Netzer:
Detecting Race Conditions in Parallel Programs that Use One Semaphore.
WADS 1993: 471-482 |
| 17 | | Philip N. Klein,
Clifford Stein:
A Parallel Algorithm for Approximating the Minimum Cycle Cover.
Algorithmica 9(1): 23-31 (1993) |
| 16 | | Philip N. Klein:
Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs.
J. Algorithms 14(3): 331-343 (1993) |
| 15 | | Ming-Yang Kao,
Philip N. Klein:
Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs.
J. Comput. Syst. Sci. 47(3): 459-500 (1993) |
| 14 | | Samir Khuller,
Joseph Naor,
Philip N. Klein:
The Lattice Structure of Flow in Planar Graphs.
SIAM J. Discrete Math. 6(3): 477-490 (1993) |
| 1992 |
|---|
| 13 | | R. Ravi,
Balaji Raghavachari,
Philip N. Klein:
Approximation Through Local Optimality: Designing Networks with Small Degree.
FSTTCS 1992: 279-290 |
| 12 | | Philip N. Klein,
Sairam Sairam:
A Parallel Randomized Approximation Scheme for Shortest Paths
STOC 1992: 750-758 |
| 1991 |
|---|
| 11 | | R. Ravi,
Ajit Agrawal,
Philip N. Klein:
Ordering Problems Approximated: Single-Processor Scheduling and Interval Graph Completion.
ICALP 1991: 751-762 |
| 10 | | Ajit Agrawal,
Philip N. Klein,
R. Ravi:
When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
STOC 1991: 134-144 |
| 1990 |
|---|
| 9 | | Philip N. Klein,
Ajit Agrawal,
R. Ravi,
Satish Rao:
Approximation through Multicommodity Flow
FOCS 1990: 726-737 |
| 8 | | Ming-Yang Kao,
Philip N. Klein:
Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs
STOC 1990: 181-192 |
| 7 | | Philip N. Klein,
Clifford Stein,
Éva Tardos:
Leighton-Rao Might Be Practical: Faster Approximation Algorithms for Concurrent Flow with Uniform Capacities
STOC 1990: 310-321 |
| 6 | | Philip N. Klein,
Clifford Stein:
A Parallel Algorithm for Eliminating Cycles in Undirected Graphs.
Inf. Process. Lett. 34(6): 307-312 (1990) |
| 5 | | Lisa Hellerstein,
Philip N. Klein,
Robert Wilber:
On the Time-Space Complexity of Reachability Queries for Preprocessed Graphs.
Inf. Process. Lett. 35(5): 261-267 (1990) |
| 1988 |
|---|
| 4 | | Philip N. Klein:
Efficient Parallel Algorithms for Chordal Graphs
FOCS 1988: 150-161 |
| 3 | | Philip N. Klein,
John H. Reif:
An Efficient Parallel Algorithm for Planarity.
J. Comput. Syst. Sci. 37(2): 190-246 (1988) |
| 2 | | Philip N. Klein,
John H. Reif:
Parallel Time O(log n) Acceptance of Deterministic CFLs on an Exclusive-Write P-RAM.
SIAM J. Comput. 17(3): 463-485 (1988) |
| 1986 |
|---|
| 1 | | Philip N. Klein,
John H. Reif:
An Efficient Parallel Algorithm for Planarity
FOCS 1986: 465-477 |
