☰

Philip Klein - Publications

Affiliations: 
Computer Science Brown University, Providence, RI 
Area:
Algorithms and Theory
Tree Info Similar researchers PubMed Report error

65 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2016 Borradaile G, Klein P. The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs Acm Transactions On Algorithms. 12: 1-29. DOI: 10.1145/2831235  0.667
2016 Fox K, Klein PN, Mozes S. A polynomial-time bicriteria approximation scheme for planar bisection Proceedings of the Annual Acm Symposium On Theory of Computing. 14: 841-850. DOI: 10.1145/2746539.2746564  0.451
2015 Klein PN, Mathieu C, Zhou H. Correlation clustering and two-edge-connected augmentation for planar graphs Leibniz International Proceedings in Informatics, Lipics. 30: 554-567. DOI: 10.4230/LIPIcs.STACS.2015.554  0.431
2015 Borradaile G, Klein PN, Mathieu C. A polynomial-time approximation scheme for Euclidean Steiner forest Acm Transactions On Algorithms. 11. DOI: 10.1145/2629654  0.577
2015 Klein P, Young NE. On the number of iterations for Dantzig-Wolfe optimization and packing-covering approximation algorithms Siam Journal On Computing. 44: 1154-1172. DOI: 10.1137/12087222X  0.368
2014 Demaine ED, Hajiaghayi M, Klein PN. Node-weighted steiner tree and group steiner tree in planar graphs Acm Transactions On Algorithms. 10. DOI: 10.1145/2601070  0.56
2014 Eisenstat D, Klein PN, Mathieu C. Approximating k-center in planar graphs Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 617-627.  0.353
2014 Klein PN, Marx D. A subexponential parameterized algorithm for Subset TSP on planar graphs Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 1812-1830.  0.492
2013 Eisenstat D, Klein PN. Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs Proceedings of the Annual Acm Symposium On Theory of Computing. 735-744. DOI: 10.1145/2488608.2488702  0.428
2013 Klein PN, Mozes S, Sommer C. Structured recursive separator decompositions for planar graphs in linear time Proceedings of the Annual Acm Symposium On Theory of Computing. 505-514. DOI: 10.1145/2488608.2488672  0.373
2012 Klein PN, Marx D. Solving Planar k-Terminal Cut in O(nc√k) time Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 7391: 569-580. DOI: 10.1007/978-3-642-31594-7_48  0.418
2012 Bateni M, Hajiaghayi M, Klein PN, Mathieu C. A polynomial-time approximation scheme for planar multiway cut Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 639-655.  0.49
2012 Eisenstat D, Klein P, Mathieu C. An efficient polynomial-time approximation scheme for Steiner forest in planar graphs Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 626-638.  0.414
2011 Borradaile G, Klein PN, Mozes S, Nussbaum Y, Wulff-Nilsen C. Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 170-179. DOI: 10.1137/15M1042929  0.674
2011 Klein PN, Mozes S. Multiple-source single-sink maximum flow in directed planar graphs in O(diameter·n log n) time Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6844: 571-582. DOI: 10.1007/978-3-642-22300-6_48  0.481
2011 Kawarabayashi KI, Klein PN, Sommer C. Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 6755: 135-146. DOI: 10.1007/978-3-642-22006-7_12  0.484
2010 Klein PN, Mozes S, Weimann O. Shortest paths in directed planar graphs with negative lengths: A linear-space O(n log2 n)-time algorithm Acm Transactions On Algorithms. 6. DOI: 10.1145/1721837.1721846  0.537
2009 Borradaile G, Klein P, Mathieu C. An O(n log n) approximation scheme for Steiner tree in planar graphs Acm Transactions On Algorithms. 5. DOI: 10.1145/1541885.1541892  0.681
2009 Borradaile G, Klein P. An O(n log n) algorithm for maximum st-flow in a directed planar graph Journal of the Acm. 56. DOI: 10.1145/1502793.1502798  0.68
2008 Borradaile G, Klein P. The two-edge connectivity survivable network problem in planar graphs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5125: 485-501. DOI: 10.1007/978-3-540-70575-8_40  0.667
2007 Klein PN. A Linear-time approximation scheme for TSP in undirected planar graphs with edge-weights Siam Journal On Computing. 37: 1926-1952. DOI: 10.1137/060649562  0.547
2007 Borradaile G, Klein PN, Mathieu C. Steiner tree in planar graphs: An O(n log n) approximation scheme with singly-exponential dependence on epsilon Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 4619: 275-286.  0.681
2006 Borradaile G, Klein P. An O (n log n) algorithm for maximum st-flow in a directed planar graph Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 524-533. DOI: 10.1145/1502793.1502798  0.687
2006 Klein PN. A subset spanner for planar graphs, with application to subset TSP Proceedings of the Annual Acm Symposium On Theory of Computing. 2006: 749-756.  0.487
2005 Klein PN. A linear-time approximation scheme for planar weighted TSP Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 2005: 647-656. DOI: 10.1109/SFCS.2005.7  0.528
2005 Klein PN. Multiple-source shortest paths in planar graphs Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 146-155.  0.504
2004 Sebastian TB, Klein PN, Kimia BB. Recognition of shapes by editing their shock graphs. Ieee Transactions On Pattern Analysis and Machine Intelligence. 26: 550-71. PMID 15460278 DOI: 10.1109/Tpami.2004.1273924  0.364
2004 Karger DR, Klein P, Stein C, Thorup M, Young NE. Rounding algorithms for a geometric embedding of minimum multiway cut Mathematics of Operations Research. 29: 436-461. DOI: 10.1287/Moor.1030.0086  0.477
2004 Klein PN, Krishnan R, Raghavachari B, Ravi R. Approximation algorithms for finding low-degree subgraphs Networks. 44: 203-215. DOI: 10.1002/Net.20031  0.43
2003 Klein PN, Lu HI, Netzer RHB. Detecting race conditions in parallel programs that use semaphores Algorithmica (New York). 35: 321-345. DOI: 10.1007/s00453-002-1004-3  0.351
2002 Klein P. Preprocessing an undirected planar network to enable fast approximate distance queries Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 6: 820-827.  0.467
2000 Klein P, Tirthapura S, Sharvit D, Kimia B. Tree-edit-distance algorithm for comparing simple, closed shapes Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 696-704.  0.395
1998 Tirthapura S, Sharvit D, Klein P, Kimia BB. Indexing based on edit-distance matching of shape graphs Proceedings of Spie - the International Society For Optical Engineering. 3527: 25-36. DOI: 10.1117/12.325825  0.39
1998 Arora S, Grigni M, Karger D, Klein P, Woloszyn A. Polynomial-time approximation scheme for weighted planar graph TSP Proceedings of the Annual Acm-Siam Symposium On Discrete Algorithms. 33-41.  0.508
1998 Klein PN. Computing the edit-distance between unrooted ordered trees Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1461: 91-102.  0.348
1998 Klein PN, Subramanian S. A fully dynamic approximation scheme for shortest paths in planar graphs Algorithmica (New York). 22: 235-249.  0.56
1998 Klein PN, Lu HI. Space-efficient approximation algorithms for MAXCUT and COLORING semidefinite programs Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1533: 387-398.  0.482
1997 Klein PN, Subramanian S. A Randomized Parallel Algorithm for Single-Source Shortest Paths Journal of Algorithms. 25: 205-220.  0.363
1997 Klein PN, Plotkin SA, Rao S, Tardos E. Approximation Algorithms for Steiner and Directed Multicuts Journal of Algorithms. 22: 241-269.  0.454
1997 Henzinger MR, Klein P, Rao S, Subramanian S. Faster Shortest-Path Algorithms for Planar Graphs Journal of Computer and System Sciences. 55: 3-23.  0.523
1996 Klein PN, Lu HI, Netzer RHB. Race-condition detection in parallel computation with semaphores (Extended abstract) Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1136: 445-459. DOI: 10.1007/3-540-61680-2_74  0.439
1996 Klein P, Lu HI. Efficient approximation algorithms for semidefinite programs arising from MAX CUT and COLORING Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 338-347.  0.469
1996 Klein PN. Efficient parallel algorithms for chordal graphs Siam Journal On Computing. 25: 797-827.  0.499
1996 Cole R, Klein PN, Tarjan RE. Finding minimum spanning forests in logarithmic time and linear work using random sampling Annual Acm Symposium On Parallel Algorithms and Architectures. 243-250.  0.48
1995 Karger DR, Klein PN, Tarjan RE. Randomized linear-time algorithm to find minimum spanning trees Journal of the Acm. 42: 321-328. DOI: 10.1145/201019.201022  0.415
1995 Agrawal A, Klein P, Ravi R. When trees collide: an approximation algorithm for the generalized steiner problem on networks Siam Journal On Computing. 24: 440-456. DOI: 10.1137/S0097539792236237  0.397
1995 Klein P, Rao S, Agrawal A, Ravi R. An approximate max-flow min-cut relation for undirected multicommodity flow, with applications Combinatorica. 15: 187-202. DOI: 10.1007/Bf01200755  0.348
1995 Klein P, Ravi R. A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees Journal of Algorithms. 19: 104-115. DOI: 10.1006/Jagm.1995.1029  0.496
1994 Klein P, Plotkin S, Stein C, Tardos E. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts Siam Journal On Computing. 23: 466-487. DOI: 10.1137/S0097539792241175  0.561
1994 Klein PN. A data structure for bicategories, with application to speeding up an approximation algorithm Information Processing Letters. 52: 303-307. DOI: 10.1016/0020-0190(94)00156-1  0.521
1994 Klein PN, Tarjan RE. Randomized linear-time algorithm for finding minimum spanning trees Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 9-15.  0.415
1993 Khuller S, Naor J(, Klein P. The Lattice Structure of Flow in Planar Graphs Siam Journal On Discrete Mathematics. 6: 477-490. DOI: 10.1137/0406038  0.533
1993 Kao MY, Klein PN. Towards overcoming the transitive-closure bottleneck: Efficient parallel algorithms for planar digraphs Journal of Computer and System Sciences. 47: 459-500. DOI: 10.1016/0022-0000(93)90042-U  0.379
1993 Klein P, Stein C. A parallel algorithm for approximating the minimum cycle cover Algorithmica. 9: 23-31. DOI: 10.1007/Bf01185336  0.452
1993 Klein PN. Parallelism, Preprocessing, and Reachability: A Hybrid Algorithm for Directed Graphs Journal of Algorithms. 14: 331-343. DOI: 10.1006/jagm.1993.1017  0.471
1993 Klein PN, Subramanian S. Linear-processor polylog-time algorithm for shortest paths in planar graphs Annual Symposium On Foundatons of Computer Science (Proceedings). 259-270.  0.568
1993 Klein P, Plotkin SA, Rao S. Excluded minors, network decomposition, and multicommodity flow Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 682-690.  0.513
1992 Klein PN, Sairam S. Parallel randomized approximation scheme for shortest paths Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 750-758.  0.463
1990 Hellerstein L, Klein P, Wilber R. On the time-space complexity of reachability queries for preprocessed graphs Information Processing Letters. 35: 261-267. DOI: 10.1016/0020-0190(90)90055-3  0.503
1990 Klein P, Stein C. A parallel algorithm for eliminating cycles in undirected graphs Information Processing Letters. 34: 307-312. DOI: 10.1016/0020-0190(90)90015-P  0.545
1990 Klein P, Agrawal A, Ravi R, Rao S. Approximation through multicommodity flow Annual Symposium On Foundations of Computer Science - Proceedings. 2: 726-737.  0.43
1990 Klein P, Stein C, Tardos E. Leighton-Rao might be practical. Faster approximation algorithms for concurrent flow with uniform capacities . 310-321.  0.503
1990 Kao MY, Klein PN. Towards overcoming the transitive-closure bottleneck. Efficient parallel algorithms for planar digraphs . 181-192.  0.377
1988 Klein PN, Reif JH. Parallel time O(log n) acceptance of deterministic CFLs on an exclusive-write P-RAM Siam Journal On Computing. 17: 463-485.  0.409
1986 Klein PN, Reif JH. EFFICIENT PARALLEL ALGORITHM FOR PLANARITY Annual Symposium On Foundations of Computer Science (Proceedings). 465-477.  0.513
Show low-probability matches.