![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Philip N. Klein
- > Startseite > Persons
Person information
- affiliation: Brown University, Department of Computer Science, Providence, RI, USA
Refine list
![note](https://dblp.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2023
- [j35]Philip N. Klein, Claire Mathieu, Hang Zhou:
Correlation Clustering and Two-Edge-Connected Augmentation for Planar Graphs. Algorithmica 85(10): 3024-3057 (2023) - 2021
- [c70]Vincent Cohen-Addad, Philip N. Klein, Dániel Marx, Archer Wheeler, Christopher Wolfram:
On the Computational Tractability of a Geographic Clustering Problem Arising in Redistricting. FORC 2021: 3:1-3:18 - [c69]Vincent Cohen-Addad, Anupam Gupta
, Philip N. Klein, Jason Li:
A quasipolynomial (2 + ε)-approximation for planar sparsest cut. STOC 2021: 1056-1069 - [i23]Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein, Jason Li:
A Quasipolynomial (2+ε)-Approximation for Planar Sparsest Cut. CoRR abs/2105.15187 (2021) - 2020
- [c68]Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le:
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. FOCS 2020: 589-600 - [c67]Archer Wheeler, Philip N. Klein:
The impact of highly compact algorithmic redistricting on the rural-versus-urban balance. SIGSPATIAL/GIS 2020: 397-400 - [c66]Amir Abboud, Vincent Cohen-Addad, Philip N. Klein:
New hardness results for planar graph problems in p and an algorithm for sparsest cut. STOC 2020: 996-1009 - [i22]Amir Abboud, Vincent Cohen-Addad, Philip N. Klein:
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut. CoRR abs/2007.02377 (2020) - [i21]Vincent Cohen-Addad, Philip N. Klein, Dániel Marx:
On the computational tractability of a geographic clustering problem arising in redistricting. CoRR abs/2009.00188 (2020) - [i20]Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, Hung Le:
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs. CoRR abs/2009.05039 (2020)
2010 – 2019
- 2019
- [j34]Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu:
Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. SIAM J. Comput. 48(2): 644-667 (2019) - [c65]Eli Fox-Epstein, Philip N. Klein, Aaron Schild:
Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems. SODA 2019: 1069-1088 - [c64]Amariah Becker, Philip N. Klein, Aaron Schild:
A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs. WADS 2019: 99-111 - [i19]Amariah Becker, Philip N. Klein, Aaron Schild:
A PTAS for Bounded-Capacity Vehicle Routing in Planar Graphs. CoRR abs/1901.07032 (2019) - [i18]Stephen Jue, Philip N. Klein:
A near-linear time minimum Steiner cut algorithm for planar graphs. CoRR abs/1912.11103 (2019) - 2018
- [c63]Amariah Becker, Philip N. Klein, David Saulpic:
Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension. ESA 2018: 8:1-8:15 - [c62]Vincent Cohen-Addad, Philip N. Klein, Neal E. Young
:
Balanced centroidal power diagrams for redistricting. SIGSPATIAL/GIS 2018: 389-396 - 2017
- [j33]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. SIAM J. Comput. 46(4): 1280-1303 (2017) - [c61]Amariah Becker, Philip N. Klein, David Saulpic:
A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs. ESA 2017: 12:1-12:15 - [c60]Amariah Becker, Eli Fox-Epstein, Philip N. Klein, David Meierfrankenfeld:
Engineering an Approximation Scheme for Traveling Salesman in Planar Graphs. SEA 2017: 8:1-8:17 - [e1]Philip N. Klein:
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19. SIAM 2017, ISBN 978-1-61197-478-2 [contents] - [i17]Amariah Becker, Philip N. Klein, David Saulpic:
Polynomial-Time Approximation Schemes for k-Center and Bounded-Capacity Vehicle Routing in Metrics with Bounded Highway Dimension. CoRR abs/1707.08270 (2017) - [i16]Vincent Cohen-Addad, Philip N. Klein, Neal E. Young:
Balanced power diagrams for redistricting. CoRR abs/1710.03358 (2017) - 2016
- [j32]Glencora Borradaile, Philip N. Klein:
The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs. ACM Trans. Algorithms 12(3): 30:1-30:29 (2016) - [c59]Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu:
Local Search Yields Approximation Schemes for k-Means and k-Median in Euclidean and Minor-Free Metrics. FOCS 2016: 353-364 - [c58]Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, David Meierfrankenfeld:
Approximating connectivity domination in weighted bounded-genus graphs. STOC 2016: 584-597 - [i15]Vincent Cohen-Addad, Philip N. Klein, Claire Mathieu:
The power of local search for clustering. CoRR abs/1603.09535 (2016) - [i14]Jeff Erickson, Philip N. Klein, Dániel Marx, Claire Mathieu:
Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 16221). Dagstuhl Reports 6(5): 94-116 (2016) - 2015
- [j31]Philip N. Klein, Neal E. Young
:
On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms. SIAM J. Comput. 44(4): 1154-1172 (2015) - [j30]Glencora Borradaile, Philip N. Klein, Claire Mathieu:
A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. ACM Trans. Algorithms 11(3): 19:1-19:20 (2015) - [c57]Philip N. Klein, Claire Mathieu, Hang Zhou:
Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs. STACS 2015: 554-567 - [c56]Kyle Fox, Philip N. Klein, Shay Mozes
:
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection. STOC 2015: 841-850 - [i13]Kyle Fox, Philip N. Klein, Shay Mozes:
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection. CoRR abs/1504.08008 (2015) - 2014
- [b1]Philip N. Klein:
A Cryptography Primer: Secrets and Promises. Cambridge University Press 2014, ISBN 9781139084772 - [j29]Erik D. Demaine, Mohammad Taghi Hajiaghayi, Philip N. Klein:
Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. ACM Trans. Algorithms 10(3): 13:1-13:20 (2014) - [c55]David Eisenstat, Philip N. Klein, Claire Mathieu:
Approximating k-center in planar graphs. SODA 2014: 617-627 - [c54]Philip N. Klein, Dániel Marx:
A subexponential parameterized algorithm for Subset TSP on planar graphs. SODA 2014: 1812-1830 - 2013
- [c53]Philip N. Klein, Shay Mozes
, Christian Sommer:
Structured recursive separator decompositions for planar graphs in linear time. STOC 2013: 505-514 - [c52]David Eisenstat, Philip N. Klein:
Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs. STOC 2013: 735-744 - [i12]Glencora Borradaile, Philip N. Klein:
The two-edge connectivity survivable-network design problem in planar graphs. CoRR abs/1302.2184 (2013) - [i11]Glencora Borradaile, Philip N. Klein, Claire Mathieu:
A polynomial-time approximation scheme for Euclidean Steiner forest. CoRR abs/1302.7270 (2013) - [i10]Glencora Borradaile, Philip N. Klein, Dániel Marx, Claire Mathieu:
Algorithms for Optimization Problems in Planar Graphs (Dagstuhl Seminar 13421). Dagstuhl Reports 3(10): 36-57 (2013) - 2012
- [c51]Philip N. Klein, Dániel Marx:
Solving Planar k -Terminal Cut in $O(n^{c \sqrt{k}})$ Time. ICALP (1) 2012: 569-580 - [c50]David Eisenstat, Philip N. Klein, Claire Mathieu:
An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. SODA 2012: 626-638 - [c49]MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Philip N. Klein, Claire Mathieu:
A polynomial-time approximation scheme for planar multiway cut. SODA 2012: 639-655 - [i9]Philip N. Klein, Shay Mozes, Christian Sommer:
Structured Recursive Separator Decompositions for Planar Graphs in Linear Time. CoRR abs/1208.2223 (2012) - 2011
- [c48]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: 170-179 - [c47]Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer:
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs. ICALP (1) 2011: 135-146 - [c46]Philip N. Klein, Shay Mozes
:
Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time. WADS 2011: 571-582 - [i8]Philip N. Klein, Shay Mozes:
Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter*n*log(n)) Time. CoRR abs/1104.4728 (2011) - [i7]Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer:
Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus, and Minor-Free Graphs. CoRR abs/1104.5214 (2011) - [i6]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 abs/1105.2228 (2011) - [i5]David Eisenstat, Philip N. Klein, Claire Mathieu:
An efficient polynomial-time approximation scheme for Steiner forest in planar graphs. CoRR abs/1110.1320 (2011) - 2010
- [j28]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 Trans. Algorithms 6(2): 30:1-30:18 (2010) - [i4]Philip N. Klein, Shay Mozes:
Multiple-source single-sink maximum flow in directed planar graphs in $O(n^{1.5} \log n)$ time. CoRR abs/1008.5332 (2010)
2000 – 2009
- 2009
- [j27]Glencora Borradaile, Philip N. Klein:
An O(n log n) algorithm for maximum st-flow in a directed planar graph. J. ACM 56(2): 9:1-9:30 (2009) - [j26]Glencora Borradaile, Philip N. Klein, Claire Mathieu:
An O(n log n) approximation scheme for Steiner tree in planar graphs. ACM Trans. Algorithms 5(3): 31:1-31:31 (2009) - [c45]Erik D. Demaine, MohammadTaghi Hajiaghayi, Philip N. Klein:
Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. ICALP (1) 2009: 328-340 - [c44]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 - 2008
- [j25]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) - [c43]Glencora Borradaile, Philip N. Klein, Claire Mathieu:
A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. FOCS 2008: 115-124 - [c42]Glencora Borradaile, Philip N. Klein:
The Two-Edge Connectivity Survivable Network Problem in Planar Graphs. ICALP (1) 2008: 485-501 - 2007
- [c41]Glencora Borradaile, Claire Kenyon-Mathieu, Philip N. Klein:
A polynomial-time approximation scheme for Steiner tree in planar graphs. SODA 2007: 1285-1294 - [c40]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
- [c39]Glencora Borradaile, Philip N. Klein:
An O (n log n) algorithm for maximum st-flow in a directed planar graph. SODA 2006: 524-533 - [c38]Philip N. Klein:
A subset spanner for Planar graphs, : with application to subset TSP. STOC 2006: 749-756 - 2005
- [c37]Philip N. Klein:
A linear-time approximation scheme for planar weighted TSP. FOCS 2005: 647-657 - [c36]Philip N. Klein:
Multiple-source shortest paths in planar graphs. SODA 2005: 146-155 - 2004
- [j24]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) - [j23]Philip N. Klein, Radha Krishnan, Balaji Raghavachari, R. Ravi:
Approximation algorithms for finding low-degree subgraphs. Networks 44(3): 203-215 (2004) - [j22]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) - 2003
- [j21]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) - [j20]Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia:
On Aligning Curves. IEEE Trans. Pattern Anal. Mach. Intell. 25(1): 116-125 (2003) - 2002
- [c35]Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia:
Shock-Based Indexing into Large Shape Databases. ECCV (3) 2002: 731-746 - [c34]Philip N. Klein:
Preprocessing an undirected planar network to enable fast approximate distance queries. SODA 2002: 820-827 - [i3]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) - [i2]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) - [i1]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
- [c33]Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia:
Recognition of Shapes by Editing Shock Graphs. ICCV 2001: 755-762 - [c32]Thomas B. Sebastian, Philip N. Klein, Benjamin B. Kimia:
Alignment-Based Recognition of Shape Outlines. IWVF 2001: 606-618 - [c31]Philip N. Klein, Thomas B. Sebastian, Benjamin B. Kimia:
Shape matching using edit-distance: an implementation. SODA 2001: 781-790 - 2000
- [c30]Thomas W. Doeppner Jr., Philip N. Klein, Andrew Koyfman:
Using router stamping to identify the source of IP packets. CCS 2000: 184-189 - [c29]Philip N. Klein, Srikanta Tirthapura, Daniel Sharvit, Benjamin B. Kimia:
A tree-edit-distance algorithm for comparing simple, closed shapes. SODA 2000: 696-704 - [c28]Philip N. Klein:
Finding the closest lattice vector when it's unusually close. SODA 2000: 937-941
1990 – 1999
- 1999
- [c27]Philip N. Klein, Neal E. Young
:
On the Number of Iterations for Dantzig-Wolfe Optimization and Packing-Covering Approximation Algorithms. IPCO 1999: 320-327 - [c26]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 - [p1]Philip N. Klein, Neal E. Young:
Approximation Algorithms. Algorithms and Theory of Computation Handbook 1999 - 1998
- [j19]Philip N. Klein, Sairam Subramanian:
A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs. Algorithmica 22(3): 235-249 (1998) - [c25]Philip N. Klein:
Computing the Edit-Distance between Unrooted Ordered Trees. ESA 1998: 91-102 - [c24]Philip N. Klein, Hsueh-I Lu:
Space-Efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs. ISAAC 1998: 387-396 - [c23]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 - 1997
- [j18]Philip N. Klein, Serge A. Plotkin, Satish Rao, Éva Tardos:
Approximation Algorithms for Steiner and Directed Multicuts. J. Algorithms 22(2): 241-269 (1997) - [j17]Philip N. Klein, Sairam Subramanian:
A Randomized Parallel Algorithm for Single-Source Shortest Paths. J. Algorithms 25(2): 205-220 (1997) - [j16]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
- [j15]Philip N. Klein:
Efficient Parallel Algorithms for Chordal Graphs. SIAM J. Comput. 25(4): 797-827 (1996) - [c22]Philip N. Klein, Hsueh-I Lu, Robert H. B. Netzer:
Race-Condition Detection in Parallel Computation with Semaphores (Extended Abstract). ESA 1996: 445-459 - [c21]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 - [c20]Philip N. Klein, Hsueh-I Lu:
Efficient Approximation Algorithms for Semidefinite Programs Arising from MAX CUT and COLORING. STOC 1996: 338-347 - 1995
- [j14]Philip N. Klein, Satish Rao, Ajit Agrawal, R. Ravi:
An Approximate Max-Flow Min-Cut Relation for Unidirected Multicommodity Flow, with Applications. Comb. 15(2): 187-202 (1995) - [j13]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) - [j12]Philip N. Klein, R. Ravi:
A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees. J. Algorithms 19(1): 104-115 (1995) - [j11]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
- [j10]Philip N. Klein:
A Data Structure for Bicategories, with Application to Speeding up an Approximation Algorithm. Inf. Process. Lett. 52(6): 303-307 (1994) - [j9]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) - [c19]Philip N. Klein, Robert Endre Tarjan:
A randomized linear-time algorithm for finding minimum spanning trees. STOC 1994: 9-15 - [c18]Philip N. Klein, Satish Rao, Monika Rauch, Sairam Subramanian:
Faster shortest-path algorithms for planar graphs. STOC 1994: 27-37 - 1993
- [j8]Philip N. Klein, Clifford Stein:
A Parallel Algorithm for Approximating the Minimum Cycle Cover. Algorithmica 9(1): 23-31 (1993) - [j7]Philip N. Klein:
Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs. J. Algorithms 14(3): 331-343 (1993) - [j6]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) - [j5]Samir Khuller, Joseph Naor, Philip N. Klein:
The Lattice Structure of Flow in Planar Graphs. SIAM J. Discret. Math. 6(3): 477-490 (1993) - [c17]Philip N. Klein, Sairam Subramanian:
A linear-processor polylog-time algorithm for shortest paths in planar graphs. FOCS 1993: 259-270 - [c16]Philip N. Klein, R. Ravi:
When cycles collapse: A general approximation technique for constrained two-connectivity problems. IPCO 1993: 39-55 - [c15]Philip N. Klein, R. Ravi:
A nearly best-possible approximation algorithm for node-weighted Steiner trees. IPCO 1993: 323-332 - [c14]Philip N. Klein:
On Gazit and Miller's Parallel Algorithm for Planar Separators: Achieving Greater Efficiency Through Random Sampling. SPAA 1993: 43-49 - [c13]Philip N. Klein, Serge A. Plotkin, Satish Rao:
Excluded minors, network decomposition, and multicommodity flow. STOC 1993: 682-690 - [c12]Philip N. Klein, Sairam Subramanian:
A Fully Dynamic Approximation Scheme for All-Pairs Shortest Paths in Planar Graphs. WADS 1993: 442-451 - [c11]Hsueh-I Lu, Philip N. Klein, Robert H. B. Netzer:
Detecting Race Conditions in Parallel Programs that Use One Semaphore. WADS 1993: 471-482 - 1992
- [c10]R. Ravi, Balaji Raghavachari, Philip N. Klein:
Approximation Through Local Optimality: Designing Networks with Small Degree. FSTTCS 1992: 279-290 - [c9]Philip N. Klein, Sairam Sairam:
A Parallel Randomized Approximation Scheme for Shortest Paths. STOC 1992: 750-758 - 1991
- [c8]James M. Borger, Sarah Kang, Philip N. Klein:
Approximating Concurrent Flow with Unit Demands and Capacities: An Implementation. Network Flows And Matching 1991: 371-386 - [c7]R. Ravi, Ajit Agrawal, Philip N. Klein:
Ordering Problems Approximated: Single-Processor Scheduling and Interval Graph Completion. ICALP 1991: 751-762 - [c6]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
- [j4]Philip N. Klein, Clifford Stein:
A Parallel Algorithm for Eliminating Cycles in Undirected Graphs. Inf. Process. Lett. 34(6): 307-312 (1990) - [j3]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) - [c5]Philip N. Klein, Ajit Agrawal, R. Ravi, Satish Rao:
Approximation through Multicommodity Flow. FOCS 1990: 726-737 - [c4]Ming-Yang Kao, Philip N. Klein:
Towards Overcoming the Transitive-Closure Bottleneck: Efficient Parallel Algorithms for Planar Digraphs. STOC 1990: 181-192 - [c3]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
1980 – 1989
- 1988
- [j2]Philip N. Klein, John H. Reif:
An Efficient Parallel Algorithm for Planarity. J. Comput. Syst. Sci. 37(2): 190-246 (1988) - [j1]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) - [c2]Philip N. Klein:
Efficient Parallel Algorithms for Chordal Graphs. FOCS 1988: 150-161 - 1986
- [c1]Philip N. Klein, John H. Reif:
An Efficient Parallel Algorithm for Planarity. FOCS 1986: 465-477
Coauthor Index
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-05-06 21:12 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint