71 citations · 164 across the 18 of their papers we have counts for
22 papers
Simple analysis of an algorithm for multiple-source shortest paths in planar graphs
Philip N. Klein
This paper addresses the following problem: given a planar embedding graph, compute a representation of the shortest-path trees rooted at all the boundary nodes of the graph. Klein…
A Quasipolynomial -Approximation for Planar Sparsest Cut
Vincent Cohen-Addad, Anupam Gupta, Philip N. Klein +1
The (non-uniform) sparsest cut problem is the following graph-partitioning problem: given a "supply" graph, and demands on pairs of vertices, delete some subset of supply edges to…
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein +1
Understanding the structure of minor-free metrics, namely shortest path metrics obtained over a weighted graph excluding a fixed minor, has been an important research direction sin…
On the computational tractability of a geographic clustering problem arising in redistricting
Vincent Cohen-Addad, Philip N. Klein, Dániel Marx
Redistricting is the problem of dividing a state into a number of regions, called districts. Voters in each district elect a representative. The primary criteria are: each dist…
New Hardness Results for Planar Graph Problems in P and an Algorithm for Sparsest Cut
Amir Abboud, Vincent Cohen-Addad, Philip N. Klein
The Sparsest Cut is a fundamental optimization problem that has been extensively studied. For planar inputs the problem is in and can be solved in time if all…
A near-linear time minimum Steiner cut algorithm for planar graphs
Stephen Jue, Philip N. Klein
We consider the Minimum Steiner Cut problem on undirected planar graphs with non-negative edge weights. This problem involves finding the minimum cut of the graph that separates a…