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.
| 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. |
| 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. |
| 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. |
| Year | Degree | Institution |
|---|---|---|
| 1988 | PhD | Massachusetts Institute of Technology |
| 1986 | MS | Massachusetts Institute of Technology |
| 1984 | BA | Harvard University |
Presidential Young Investigator Award,
Hoopes Prize
Fellow of the ACM
| CSCI 0170 - Computer Science: An Integrated Introduction |
| CSCI 0500 - Data Structures, Algorithms, and Intractability: An Introduction |
| CSCI 0530 - Directions: The Matrix in Computer Science |
| CSCI 1570 - Design and Analysis of Algorithms |
| CSCI 1951I - CS for Social Change |
| CSCI 2500A - Advanced Algorithms |
| CSCI 2500B - Optimization Algorithms for Planar Graphs |
| CSCI 2500C - Graph Theory and Algorithms |
| CSCI 2510 - Approximation Algorithms |
