article no. SS971493 Faster Shortest-Path Algorithms for Planar Graphs (2008)
Monika R. Henzinger, Philip Klein, Satish Rao, Sairam Subramanian
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph...
Philip Klein, Srikanta Tirthapura, Daniel Sharvit, Ben Kimia
tree-edit-distance algorithm for comparing simple, closed shapes
THELATTICESTRUCTUREOFFLOWINPLANARGRAPHS* (2008)
Samir Khullert, Joseph (seffi Naoi:t, Philip Klein
Abstract. Flow in planar graphs has been extensively studied, and very efficient algorithms have been developed to compute max-flows, min-cuts, and circulations. Intimate connections between...
© 2004 INFORMS Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut (2008)
David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young
Given an undirected graph with edge costs and a subset of k ≥ 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others....
On the Weak mod m Representation of Boolean Functions (2007)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
one article at a time in L ATEX source form on the Internet. Pagination
Sanjeev Arora, Princeton U, David Karger, Philip Klein, Brown U, Andrzej Woloszyn, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young
Given an undirected graph with edge costs and a subset of
Sanjeev Arora, Princeton U, David Karger, Philip Klein, Brown U, Andrzej Woloszyn, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
A Parallel Algorithm for Approximating the Minimum Cycle Cover (2007)
Philip Klein, Cambridge Ma, Clifford Stein
We address the problem of approximating a minimum cycle cover in parallel. We give the first efficient parallel algorithm for finding an approximation to a minimum cycle cover. Our algorithm finds a...
David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young
Given an undirected graph with edge costs and a subset of k 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The...
Philip Klein, Serge Plotkin, Clifford Stein, Cambridge Ma, Eva Tardos
Faster approximation algorithms for the unit capacity concurrent
Technological Delivery Methods for Community Safety Messages (2007)
Larissa Amendola, Diana Damyanova, Stacie Gutowski, Victor Herrera, Larissa Amendola, Diana Damyanova, ...
i Community safety messages are designed to help educate the public. This project, sponsored by the Australasian Fire Authorities Council was designed to help improve safety message delivery to young...
A polynomial-time approximation scheme for Steiner tree in planar graphs (2007)
Glencora Borradaile, Claire Kenyon-mathieu, Philip Klein
We give an O(n log n) approximation scheme for Steiner tree in planar graphs. 1
A polynomial-time approximation scheme for Steiner tree in planar graphs (2007)
Glencora Borradaile, Claire Kenyon-mathieu, Philip Klein
We give an O(n log n) approximation scheme for Steiner tree in planar graphs. 1
We start with definitions given by... In this paper we give a natural probability distribution of fractional packing instances such that, for an instance chosen at random, with probability 1 - o(1)...
Finding the closest lattice vector when it's unusually close (2000)
We show how randomized rounding can be applied to finding the closest lattice vector. Given the basis of a lattice, and given a vector x not in the lattice, the heuristic will with high probability...
Finding the Closest Lattice Vector When It's Unusually Close (2000)
We show how randomized rounding can be applied to nding the closest lattice vector. Given the basis of a lattice, and given a vector x not in the lattice, the heuristic will with high probability...
A Tree-Edit-Distance Algorithm for Comparing Simple, Closed Shapes (2000)
Philip Klein, Srikanta Tirthapura, Daniel Sharvit, Ben Kimia
We discuss a graph-algorithmic approach to comparing shapes. We focus in this paper on comparing simple closed curves in the plane. Our approach is to (1) represent such a shape by its skeleton,...
We start with definitions given by Plotkin, Shmoys, and Tardos [16]. Given A ∈ IR m×n, b ∈ IR m and a polytope P ⊆ IR n,thefractional packing problem is to find an x ∈ P such that Ax ≤ b...
1
Rounding algorithms for a geometric embedding of minimum multiway cut (1999)
David R. Karger, Philip Klein, Cliff Stein, Mikkel Thorup, Neal E. Young
Given an undirected graph with edge costs and a subset of k 3 nodes called terminals, a multiway, or k-way, cut is a subset of the edges whose removal disconnects each terminal from the others. The...
Indexing based on edit-distance matching of shape graphs (1998)
Srikanta Tirthapura, Daniel Sharvit, Philip Klein, Benjamin B. Kimia
We are investigating a graph matching approach for indexing into pictorial databases using shock graphs, a symmetry-based representation of shape. Each shape (or a collection of edge elements) is...
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP (1998)
Sanjeev Arora, Michelangelo Grigni, Princeton U, David Karger, Philip Klein, Brown U, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP (1998)
Sanjeev Arora, Michelangelo Grigni, Princeton U, David Karger, Philip Klein, Brown U, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
Indexing based on edit-distance matching of shape graphs (1998)
Srikanta Tirthapura, Daniel Sharvit, Philip Klein, Benjamin B. Kimia
We are investigating a graph matching approach for indexing into pictorial databases using shock graphs, a symmetry-based representation of shape. Each shape (or a collection of edge elements) is...
A Polynomial-Time Approximation Scheme for Weighted Planar Graph TSP (1997)
Graph Tsp, Michelangelo Grigni, Sanjeev Arora, Princeton U, David Karger, Philip Klein, ...
Given a planar graph on n nodes with costs (weights) on its edges, define the distance between nodes i and j as the length of the shortest path between i and j. Consider this as an instance of metric...
Philip N. Klein, Philip Klein, Hsueh-i Lu, Hsueh-i Lu
The best known approximation algorithm for graph MAX CUT, due to Goemans and Williamson, first finds the optimal solution a semidefinite program and then derives a graph cut from that solution....
Space-efficient Approximation Algorithms for MAXCUT and COLORING Semidefinite Programs (1996)
The essential part of the best known approximation algorithm for graph MAXCUT is approximately solving MAXCUT's semidefinite relaxation. For a graph with n nodes and m edges, previous work on...
The best known approximation algorithm for graph MAX CUT, due to Goemans and Williamson, first finds the optimal solution of a semidefinite program and then derives a graph cut from that solution....
Symmetric Logspace is Closed Under Complement (1995)
Noam Nisan, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 st connectivity problem to its complement. This shows that SL = coSL. 1 Introduction This paper deals with the complexity...
On the Weak mod m Representation of Boolean Functions (1995)
Vince Grolmusz, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
Let P be a polynomial over the ring of mod m integers. P weakly represents Boolean function f : f0; 1g n ! f0; 1g if there is a subset S ` f0; 1; : : : ; m \Gamma 1g such that f(x) = 0 if and only if...
Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions (1995)
Pankaj Agarwal, Joan Feigenbaum, Carsten Lund, Andrew Goldberg, Ketan Mulmuley, ...
We initiate an investigation of probabilistically checkable debate systems (PCDS), a natural generalization of probabilistically checkable proof systems (PCPS). A PCDS for a language L consists of a...
Nils Klarlund, Dexter Kozen, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, ...
Rabin conditions are a general class of properties of infinite sequences that encompass most known automata-theoretic acceptance conditions and notions of fairness. In this paper, we introduce a...
Symmetric Logspace is Closed under Complement (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 s--t connectivity problem to its complement. This shows that SL = coSL.
[ii] Chicago Journal of Theoretical Computer Science 1995-3Rabin Measures (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
Published one article at a time in LATEX source form on the Internet. Pagination
Ajit Agrawal, Ajit Agrawal, Philip Klein, Philip Klein, R. Ravi, R. Ravi
We give the first approximation algorithm for the generalized network Steiner problem, a problem in network design. An instance consists of a network with link-costs and, for each pair fi; jg of...
Faster Shortest-Path Algorithms for Planar Graphs (1994)
Monika R. Henzinger, Philip Klein, Satish Rao, Sairam Subramanian
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph...
Faster Shortest-Path Algorithms for Planar Graphs (1994)
Sairam Subramanian, Philip Klein, Philip Klein, Satish Rao, Satish Rao, Monika Rauch, ...
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edgelengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph...
A nearly best-possible approximation algorithm for node-weighted Steiner trees (1993)
Philip Klein, Philip Klein, R. Ravi, R. Ravi
We give the first approximation algorithm for the node-weighted Steiner tree problem. Its performance guarantee is within a constant factor of the best possible unless ~ P ' NP . Our algorithm...
R. Ravi, R. Ravi, Philip Klein, Philip Klein
We present a general approximation technique for a class of network design problems where we seek a network of minimum cost that satisfies certain communication requirements and is resilient to...
Excluded Minors, Network Decomposition, and Multicommodity Flow (1993)
Philip Klein, Serge A. Plotkin, Satish Rao
In this paper we show that, given a graph and parameters ffi and r, we can find either a Kr;r minor or an edge-cut of size O(mr=ffi) whose removal yields components of weak diameter O(r 2 ffi); i.e.,...
Philip Klein Computer, Philip Klein, Serge Plotkin, Clifford Stein, Cambridge Ma, Eva Tardos
In this paper, we describe new algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities. Our algorithms are much faster than previously known...
Philip Klein, Serge Plotkin, Clifford Stein, Éva Tardos, Cambridge Ma, Eva Tardos
In this paper, we describe new algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities. Our algorithms are much faster than previously known...