Klein, Philip

Advanced search… Manage your Profile

Philip Klein

Professor of Computer Science

Overview

Professor Klein received an undergraduate degree in Applied Mathematics from Harvard and a doctoral degree in Computer Science from MIT. He was a postdoctoral fellow at Harvard before coming to Brown. He received a National Science Foundation Presidential Young Investigator Award and a Philip J. Bray Award for Teaching Excellence. He is a Fellow of the Association for Computing Machinery.

Brown Affiliations

Computer Science

Research Areas

Algorithms | approximation algorithms | combinatorial optimization | graphs | network design | networks | planar graphs | primal-dual | Steiner tree | traveling salesperson | TSP

Publications

Borradaile, Glencora, Klein, Philip. "The Two-Edge Connectivity Survivable-Network Design Problem in Planar Graphs." ACM Transactions on Algorithms, vol. 12, no. 3, 2016, pp. 1-29.

Borradaile, Glencora, Klein, Philip N., Mathieu, Claire. "A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest." ACM Transactions on Algorithms, vol. 11, no. 3, 2015, pp. 1-20.

Klein, Philip, Young, Neal E. "On the Number of Iterations for Dantzig--Wolfe Optimization and Packing-Covering Approximation Algorithms." SIAM J. Comput., vol. 44, no. 4, 2015, pp. 1154-1172.

Eisenstat, David, Klein, Philip N. "Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs." Proceedings of the 45th annual ACM symposium on Symposium on theory of computing - STOC '13, 2013.

Demaine, Erik D., Hajiaghayi, Mohammadtaghi, Klein, Philip N. "Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs." ACM Transactions on Algorithms, vol. 10, no. 3, 2013, pp. 1-20.

Klein, Philip N., Mozes, Shay, Sommer, Christian. "Structured recursive separator decompositions for planar graphs in linear time." Proceedings of the 45th annual ACM symposium on Symposium on theory of computing - STOC '13, 2013.

Klein, Philip N., Marx, Dániel. "Solving Planar k -Terminal Cut in $O(n^{c sqrt{k}})$ Time." Automata, Languages, and Programming, 2012, pp. 569-580.

Logan, John R., Spielman, Seth, Xu, Hongwei, Klein, Philip N. "Identifying and Bounding Ethnic Neighborhoods." Urban Geography, vol. 32, no. 3, 2011, pp. 334-359.

Full Text PubMed

Kawarabayashi, Ken-ichi, Klein, Philip N., Sommer, Christian. "Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs." Automata, Languages and Programming, 2011, pp. 135-146.

Borradaile, Glencora, Klein, Philip N., Mozes, Shay, Nussbaum, Yahav, Wulff-Nilsen, Christian. "Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time." 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011.

Klein, Philip N., Mozes, Shay. "Multiple-Source Single-Sink Maximum Flow in Directed Planar Graphs in O(diameter · n log n) Time." Lecture Notes in Computer Science, 2011, pp. 571-582.

Klein, Philip N., Mozes, Shay, Weimann, Oren. "Shortest paths in directed planar graphs with negative lengths." ACM Transactions on Algorithms, vol. 6, no. 2, 2010, pp. 1-18.

Borradaile, Glencora, Klein, Philip. "An O ( n log n ) algorithm for maximum st -flow in a directed planar graph." Journal of the ACM, vol. 56, no. 2, 2009, pp. 1-30.

Borradaile, Glencora, Klein, Philip, Mathieu, Claire. "An O ( n log n ) approximation scheme for Steiner tree in planar graphs." ACM Transactions on Algorithms, vol. 5, no. 3, 2009, pp. 1-31.

Demaine, Erik D., Hajiaghayi, MohammadTaghi, Klein, Philip N. "Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs." Automata, Languages and Programming, 2009, pp. 328-340.

Klein, Philip N. "A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights." SIAM J. Comput., vol. 37, no. 6, 2008, pp. 1926-1952.

Borradaile, Glencora, Klein, Philip N., Mathieu, Claire. "A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest." 2008 49th Annual IEEE Symposium on Foundations of Computer Science, 2008.

Borradaile, Glencora, Klein, Philip. "The Two-Edge Connectivity Survivable Network Problem in Planar Graphs." Automata, Languages and Programming, 2008, pp. 485-501.

Borradaile, Glencora, Klein, Philip N., Mathieu, Claire. "Steiner Tree in Planar Graphs: An O(nlogn) Approximation Scheme with Singly-Exponential Dependence on Epsilon." Lecture Notes in Computer Science, 2007, pp. 275-286.

Klein, Philip N. "A subset spanner for Planar graphs,." Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06, 2006.

Borradaile, Glencora, Klein, Philip. "An O (n log n) algorithm for maximum st -flow in a directed planar graph." Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06, 2006.

Klein, P.N. "A linear-time approximation scheme for planar weighted TSP." 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005.

Klein, Philip N., Krishnan, Radha, Raghavachari, Balaji, Ravi, R. "Approximation algorithms for finding low-degree subgraphs." Networks, vol. 44, no. 3, 2004, pp. 203-215.

Sebastian, T.B., Klein, P.N., Kimia, B.B. "Recognition of shapes by editing their shock graphs." IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 26, no. 5, 2004, pp. 550-571.

Full Text PubMed

Karger, David R., Klein, Philip, Stein, Cliff, Thorup, Mikkel, Young, Neal E. "Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut." Mathematics of Operations Research, vol. 29, no. 3, 2004, pp. 436-461.