The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Philip N. Klein: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

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

  68. A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. [Citation Graph (, )][DBLP]


  69. The Two-Edge Connectivity Survivable Network Problem in Planar Graphs. [Citation Graph (, )][DBLP]


  70. Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. [Citation Graph (, )][DBLP]


  71. Shortest paths in directed planar graphs with negative lengths: a linear-space O(n log2 n)-time algorithm. [Citation Graph (, )][DBLP]


  72. Multiple-source single-sink maximum flow in directed planar graphs in $O(n^{1.5} \log n)$ time [Citation Graph (, )][DBLP]


Search in 0.057secs, Finished in 0.059secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002