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 minimize the ratio of the supply edges cut to the total demand of the pairs separated by this deletion. Despite much effort, there are only a handful of nontrivial classes of supply graphs for which constant-factor approximations are known.

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 since the fundamental work of Robertson and Seymour. A fundamental idea that helps both to understand the structural properties of these metrics and lead to strong algorithmic results is to construct a “small-complexity” graph that approximately preserves distances between pairs of points of the metric. We show the two following structural results for minor-free metrics: 1) Construction of a light subset spanner. Given a subset of vertices called terminals, and ε, in polynomial time we construct a sub graph that preserves all pairwise distances between terminals up to a multiplicative 1+ε factor, of total weight at most Oε(1) times the weight of the minimal Steiner tree spanning the terminals. 2) Construction of a stochastic metric embedding into low treewidth graphs with expected additive distortion εD. Namely, given a minor-free graph G = (V, E, w) of diameter D, and parameter ε, we construct a distribution D over dominating metric embeddings into treewidth- Oε(logn) graphs such that ∀u, v ∈ V, \mathbbEf ~ D[dH(f(u), f(v))] ≤ dG(u, v)+εD. Our results have the following algorithmic consequences: (1) the first efficient approximation scheme for subset TSP in minor-free metrics; (2) the first approximation scheme for bounded-capacity vehicle routing in minor-free metrics; (3) the first efficient approximation scheme for bounded-capacity vehicle routing on bounded genus metrics. En route to the latter result, we design the first FPT approximation scheme for bounded-capacity vehicle routing on bounded-treewidth graphs (parameterized by the treewidth).

It is commonly believed that, in congressional and state legislature elections in the United States, rural voters have an inherent political advantage over urban voters. We study this hypothesis using an idealized redistricting method, balanced centroidal power diagrams, that achieves essentially perfect population balance while optimizing a principled measure of compactness. We find that, using this method, the degree to which rural or urban voters have a political advantage depends on the number of districts and the population density of urban areas. Moreover, we find that the political advantage in any case tends to be dramatically less than that afforded by district plans used in the real world, including district plans drawn by presumably neutral parties such as the courts. One possible explanation is suggested by the following discovery: modifying centroidal power diagrams to prefer placing boundaries along city boundaries significantly increases the advantage rural voters have over urban voters.

The Sparsest Cut is a fundamental optimization problem that have been extensively studied. For planar inputs the problem is in P and can be solved in Õ(n 3 ) time if all vertex weights are 1. Despite a significant amount of effort, the best algorithms date back to the early 90’s and can only achieve O(log n)-approximation in Õ(n) time or 3.5-approximation in Õ(n 2 ) time [Rao, STOC92]. Our main result is an Ω(n 2−ε ) lower bound for Sparsest Cut even in planar graphs with unit vertex weights, under the (min, +)-Convolution conjecture, showing that approxima- tions are inevitable in the near-linear time regime. To complement the lower bound, we provide a 3.3-approximation in near-linear time, improving upon the 25-year old result of Rao in both time and accuracy. We also show that our lower bound is not far from optimal by observing an exact algorithm with running time Õ(n 5/2 ) improving upon the Õ(n 3 ) algorithm of Park and Phillips [STOC93]. Our lower bound accomplishes a repeatedly raised challenge by being the first fine-grained lower bound for a natural planar graph problem in P. Building on our construction we prove near-quadratic lower bounds under SETH for variants of the closest pair problem in planar graphs, and use them to show that the popular Average-Linkage procedure for Hierarchical Clustering cannot be simulated in truly subquadratic time. At the core of our constructions is a diamond-like gadget that also settles the complexity of Diameter in distributed planar networks. We prove an Ω(n/ log n) lower bound on the number of communication rounds required to compute the weighted diameter of a network in the CONGET model, even when the underlying graph is planar and all nodes are D = 4 hops away from each other. This is the first poly(n) lower bound in the planar-distributed setting, and it complements the recent poly(D, log n) upper bounds of Li and Parter [STOC 2019] for (exact) unweighted diameter and for (1 + ε) approximate weighted diameter.

We show that, for any ∊ > 0, there is a deterministic embedding of edge-weighted planar graphs of diameter D into bounded-treewidth graphs. The embedding has additive error ∊D. We use this construction to obtain the first efficient bicriteria approximation schemes for weighted planar graphs addressing k-Center (equivalently d-Domination), and a metric generalization of independent set, d-independent SET. The approximation schemes employ a metric generalization of Baker's framework that is based on our embedding result.

The concept of bounded highway dimension was developed to capture observed properties of road networks. We show that a graph of bounded highway dimension with a distinguished root vertex can be embedded into a graph of bounded treewidth in such a way that u-to-v distance is preserved up to an additive error of epsilon times the u-to-root plus v-to-root distances. We show that this embedding yields a PTAS for Bounded-Capacity Vehicle Routing in graphs of bounded highway dimension. In this problem, the input specifies a depot and a set of clients, each with a location and demand; the output is a set of depot-to-depot tours, where each client is visited by some tour and each tour covers at most Q units of client demand. Our PTAS can be extended to handle penalties for unvisited clients. We extend this embedding result to handle a set S of root vertices. This result implies a PTAS for Multiple Depot Bounded-Capacity Vehicle Routing: the tours can go from one depot to another. The embedding result also implies that, for fixed k, there is a PTAS for k-Center in graphs of bounded highway dimension. In this problem, the goal is to minimize d so that there exist k vertices (the centers) such that every vertex is within distance d of some center. Similarly, for fixed k, there is a PTAS for k-Median in graphs of bounded highway dimension. In this problem, the goal is to minimize the sum of distances to the k centers.

We consider the problem of political redistricting: given the locations of people in a geographical area (e.g. a US state), the goal is to decompose the area into subareas, called districts, so that the populations of the districts are as close as possible and the districts are "compact" and "contiguous," to use the terms referred to in most US state constitutions and/or US Supreme Court rulings.

The Capacitated Vehicle Routing problem is a generalization of the Traveling Salesman problem in which a set of clients must be visited by a collection of capacitated tours. Each tour can visit at most Q clients and must start and end at a specified depot. We present the first approximation scheme for Capacitated Vehicle Routing for non-Euclidean metrics. Specifically we give a quasi-polynomial-time approximation scheme for Capacitated Vehicle Routing with fixed capacities on planar graphs. We also show how this result can be extended to bounded-genus graphs and polylogarithmic capacities, as well as to variations of the problem that include multiple depots and charging penalties for unvisited clients.

We present an implementation of a linear-time approximation scheme for the traveling salesman problem on planar graphs with edge weights. We observe that the theoretical algorithm involves constants that are too large for practical use. Our implementation, which is not subject to the theoretical algorithm's guarantee, can quickly find good tours in very large planar graphs.

We give an $O(n \log^3 n)$ algorithm that, given an $n$-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.

We give the first polynomial-time approximation schemes (PTASs) for the following problems: (1) uniform facility location in edge-weighted planar graphs, (2) k-median and k-means in edge-weighted planar graphs, (3) k-means in Euclidean space of bounded dimension. Our first and second results extend to minor-closed families of graphs. All our results extend to cost functions that are the pth power of the shortest-path distance. The algorithm is local search where the local neighborhood of a solution S consists of all solutions obtained from S by removing and adding 1/εO(1)centers.

We present a framework for addressing several problems on weighted planar graphs and graphs of bounded genus. With that framework, we derive polynomial-time approximation schemes for the following problems in planar graphs or graphs of bounded genus: edge-weighted tree cover and tour cover; vertex-weighted connected dominating set, max-weight-leaf spanning tree, and connected vertex cover. In addition, we obtain a polynomial-time approximation scheme for feedback vertex set in planar graphs. These are the first polynomial-time approximation schemes for all those problems in weighted embedded graphs. (For unweighted versions of some of these problems, polynomial-time approximation schemes were previously given using bidimensionality.)

Consider the following problem: given a graph with edge costs and a subset Q of vertices, find a minimum-cost subgraph in which there are two edge-disjoint paths connecting every pair of vertices in Q . The problem is a failure-resilient analog of the Steiner tree problem arising, for example, in telecommunications applications. We study a more general mixed-connectivity formulation, also employed in telecommunications optimization. Given a number (or requirement ) r ( v ) ∈ {0, 1, 2} for each vertex v in the graph, find a minimum-cost subgraph in which there are min { r ( u ), r ( v )} edge-disjoint u -to- v paths for every pair u , v of vertices. We address the problem in planar graphs, considering a popular relaxation in which the solution is allowed to use multiple copies of the input-graph edges (paying separately for each copy). The problem is max SNP-hard in general graphs and strongly NP-hard in planar graphs. We give the first polynomial-time approximation scheme in planar graphs. The running time is O ( n log n ). Under the additional restriction that the requirements are only non-zero for vertices on the boundary of a single face of a planar graph, we give a polynomial-time algorithm to find the optimal solution.

In correlation clustering, the input is a graph with edge-weights, where every edge is labelled either + or - according to similarity of its endpoints. The goal is to produce a partition of the vertices that disagrees with the edge labels as little as possible. In two-edge-connected augmentation, the input is a graph with edge-weights and a subset R of edges of the graph. The goal is to produce a minimum weight subset S of edges of the graph, such that for every edge in R, its endpoints are two-edge-connected in R\cup S. For planar graphs, we prove that correlation clustering reduces to two-edge-connected augmentation, and that both problems have a polynomial-time approximation scheme.

Given an undirected graph with edge costs and node weights, the minimum bisection problem asks for a partition of the nodes into two parts of equal weight such that the sum of edge costs between the parts is minimized. We give a polynomial time bicriteria approximation scheme for bisection on planar graphs. Specifically, let W be the total weight of all nodes in a planar graph G. For any constant ε > 0, our algorithm outputs a bipartition of the nodes such that each part weighs at most W/2 + ε and the total cost of edges crossing the partition is at most (1+ε) times the total cost of the optimal bisection. The previously best known approximation for planar minimum bisection, even with unit node weights, was ~O(log n). Our algorithm actually solves a more general problem where the input may include a target weight for the smaller side of the bipartition.

We give a lower bound on the iteration complexity of a natural class of Lagrangian-relaxation algorithms for approximately solving packing/covering linear programs. We show that, given an input with $m$ random 0/1-constraints on $n$ variables, with high probability, any such algorithm requires $\Omega(\rho \log(m)/\epsilon^2)$ iterations to compute a $(1+\epsilon)$-approximate solution, where $\rho$ is the width of the input. The bound is tight for a range of the parameters $(m,n,\rho,\epsilon)$. The algorithms in the class include Dantzig--Wolfe decomposition, Benders' decomposition, Lagrangian relaxation as developed by Held and Karp for lower-bounding TSP, and many others (e.g., those by Plotkin, Shmoys, and Tardos and Grigoriadis and Khachiyan). To prove the bound, we use a discrepancy argument to show an analogous lower bound on the support size of $(1+\epsilon)$-approximate mixed strategies for random two-player zero-sum 0/1-matrix games.

We give a randomized O ( n polylog n )-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed ϵ > 0 and given n terminals in the plane with connection requests between some pairs of terminals, our scheme finds a (1 + ϵ) approximation to the minimum-length forest that connects every requested pair of terminals.

Given a graph G and a subset S of vertices, the Subset TSP problem asks for a shortest closed walk in G visiting all vertices of S. The problem can be solved in time 2k · nO(1) using the classical dynamic programming algorithms of Bellman and of Held and Karp, where k = |S| and n = |V (G)|. Our main result is showing that the problem can be solved in time if G is a planar graph with weights that are integers no greater than W. While similar speedups have been observed for various paramterized problems on planar graphs, our result cannot be simply obtained as a consequence of bounding the treewidth of G or invoking bidimensionality theory. Our algorithm consists of two steps: (1) find a locally optimal solution, and (2) use it to guide a dynamic program. The proof of correctness of the algorithm depends on a treewidth bound on a graph obtained by combining an optimal solution with a locally optimal solution.

We improve the approximation ratios for two optimization problems in planar graphs. For node-weighted Steiner tree, a classical network-optimization problem, the best achievable approximation ratio in general graphs is Θ (log n ), and nothing better was previously known for planar graphs. We give a constant-factor approximation for planar graphs. Our algorithm generalizes to allow as input any nontrivial minor-closed graph family, and also generalizes to address other optimization problems such as Steiner forest, prize-collecting Steiner tree, and network-formation games. The second problem we address is group Steiner tree: given a graph with edge weights and a collection of groups (subsets of nodes), find a minimum-weight connected subgraph that includes at least one node from each group. The best approximation ratio known in general graphs is O (log 3 n ), or O (log 2 n ) when the host graph is a tree. We obtain an O (log n polyloglog n ) approximation algorithm for the special case where the graph is planar embedded and each group is the set of nodes on a face. We obtain the same approximation ratio for the minimum-weight tour that must visit each group.

We give simple linear-time algorithms for two problems in planar graphs: max st-flow in directed graphs with unit capacities, and multiple-source shortest paths in undirected graphs with unit lengths.

Given a triangulated planar graph G on n vertices and an integer r

Given an undirected graph with edge lengths and a subset of nodes (called the terminals), the multiway cut (also called the multi-terminal cut) problem asks for a subset of edges, with minimum total length, whose removal disconnects each terminal from all others. The problem generalizes minimum s-t cut, but is NP-hard for planar graphs and APX-hard for general graphs [11]. In this paper, we present a PTAS for multiway cut on planar graphs.

We give an $O(n \log^3 n)$ approximation scheme for Steiner forest in planar graphs, improving on the previous approximation scheme for this problem, which runs in $O(n^{f(\epsilon)})$ time.

We give an O(n log3n) algorithm that, given an n-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.

We give an O ( n log 2 n )-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths, and given a node s , finds the distances from s to all nodes.

We give an O(n log2 n)-time, linear-space algorithm that, given a directed planar graph with positive and negative arc-lengths, and given a node s, finds the distances from s to all nodes. The best previously known algorithm requires O(nlog3 n) time and O(n log n) space.

We give the first correct O ( n log n ) algorithm for finding a maximum st -flow in a directed planar graph. After a preprocessing step that consists in finding single-source shortest-path distances in the dual, the algorithm consists of repeatedly saturating the leftmost residual s -to- t path.

We give a Polynomial-Time Approximation Scheme (PTAS) for the Steiner tree problem in planar graphs. The running time is O ( n log n ).

We give a randomized O(n2log n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed epsi > 0 and given any n pairs of terminals in the plane, our scheme finds a (1 + epsi)- approximation to the minimum-length forest that connects every pair of terminals.

We give an algorithm requiring $O(c^{1/\epsilon^2}n)$ time to find an $\epsilon$-optimal traveling salesman tour in the shortest-path metric defined by an undirected planar graph with nonnegative edge-lengths. For the case of all lengths equal to 1, the time required is $O(c^{1/\epsilon} n)$.

Let ε>0 be a constant. For any edge-weighted planar graph G and a subset S of nodes of G, there is a subgraph H of G of weight a constant times that of the minimum Steiner tree for S such that distances in H between nodes in S are at most 1+ε times the corresponding distances in G. As a consequence, there is an O(n log n)-time approximation scheme for finding a TSP among a given subset of nodes of a planar graph. This is the first PTAS for the problem.

In view of the fact that an /spl epsi/-optimal tour can be found in the Euclidean case in time that it is polynomial with a fixed degree, independent of /spl epsi/, it seems natural to ask whether the same holds true for the planar case. We give an algorithm requiring O(c/sup 1/c2/ n) time to find an /spl epsi/-optimal traveling salesman tour in the metric defined by a planar graph with nonnegative edge-lengths.

Abstract We give quasipolynomial‐time approximation algorithms for designing networks with a minimum degree. Using our methods, one can design networks whose connectivity is specified by “proper” functions, a class of 0–1 functions indicating the number of edges crossing each cut. We also provide quasipolynomial‐time approximation algorithms for finding two‐edge‐connected spanning subgraphs of approximately minimum degree of a given two‐edge‐connected graph, and a spanning tree (branching) of approximately minimum degree of a directed graph. The degree of the output network in all cases is guaranteed to be at most (1 + ϵ) times the optimal degree, plus an additive O(log1+ϵn) for any ϵ > 0. Our analysis indicates that the degree of an optimal subgraph for each of the problems above is well estimated by certain polynomially solvable linear programs. This suggests that the linear programs we describe could be useful in obtaining optimal solutions via branch and bound. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 203–215 2004

This paper presents a novel framework for the recognition of objects based on their silhouettes. The main idea is to measure the distance between two shapes as the minimum extent of deformation necessary for one shape to match the other. Since the space of deformations is very high-dimensional, three steps are taken to make the search practical: 1) define an equivalence class for shapes based on shock-graph topology, 2) define an equivalence class for deformation paths based on shock-graph transitions, and 3) avoid complexity-increasing deformation paths by moving toward shock-graph degeneracy. Despite these steps, which tremendously reduce the search requirement, there still remain numerous deformation paths to consider. To that end, we employ an edit-distance algorithm for shock graphs that finds the optimal deformation path in polynomial time. The proposed approach gives intuitive correspondences for a variety of shapes and is robust in the presence of a wide range of visual transformations. The recognition rates on two distinct databases of 99 and 216 shapes each indicate highly successful within category matches (100 percent in top three matches), which render the framework potentially usable in a range of shape-based recognition applications.

We present a novel approach to finding a correspondence (alignment) between two curves. The correspondence is based on a notion of an alignment curve which treats both curves symmetrically. We then define a similarity metric based on the alignment curve using two intrinsic properties of the curve, namely, length and curvature. The optimal correspondence is found by an efficient dynamic-programming method both for aligning pairs of curve segments and pairs of closed curves, and is effective in the presence of a variety of transformations of the curve. Finally, the correspondence is shown in application to handwritten character recognition, prototype formation, and object recognition, and is potentially useful in other applications such as registration and tracking.

Article Free Access Share on Using router stamping to identify the source of IP packets Authors: Thomas W. Doeppner Brown University Brown UniversityView Profile , Philip N. Klein Brown University Brown UniversityView Profile , Andrew Koyfman Oracle Corporation Oracle CorporationView Profile Authors Info & Claims CCS '00: Proceedings of the 7th ACM conference on Computer and Communications SecurityNovember 2000 Pages 184–189https://doi.org/10.1145/352600.352627Published:01 November 2000Publication History 47citation993DownloadsMetricsTotal Citations47Total Downloads993Last 12 Months37Last 6 weeks11 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

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 multiway cut problem is to find a minimum-cost multiway cut. This problem is Max-SNP hard. Recently Calinescu, Karloff, and Rabani (STOC'98) gave a novel geometric relaxation of the problem and a rounding scheme that produced a (3=2 1=k)-approximation algorithm. In this paper, we study their geometric relaxation. In particular, we study the worst-case ratio between the value of the relaxation and the value of the minimum multicut (the so-called integrality gap of the relaxation). For k = 3, we show the integrality gap is 12=11, giving tight upper and lower bounds. That is, we exhibit a graph with integrality gap 12=11 and give an algorithm that finds a cut of value 12=11 times the relaxation value. This is the best possible performance guarantee for any algorithm based purely on the value of the relaxation and improves on Calinescu et al.'s factor of 7/6. We also improve the upper bounds for all larger values of k. For k = 4; 5, our best upper bounds are based on computer constructed and analyzed rounding schemes, while for k > 6 we give an algorithm with performance ratio 1:3438 k . Our results were discovered with the help of computational experiments that we also describe here. MIT Laboratory for Computer Science, Cambridge, MA 02138. [email protected]. Research supported by NSF contract CCR9624239, an Alfred P. Sloane Foundation Fellowship, and a David and Lucille Packard Foundation Fellowship. y Brown University . [email protected]. Research supported by NSF Grant CCR-9700146. z Dartmouth College. [email protected]. Research supported by NSF Caree...

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 with the source and sink on the same face. For the case where negative edge-lengths are allowed, we give an algorithm requiringO(n4/3 log(nL)) time, whereLis the absolute value of the most negative length. This algorithm can be used to obtain similar bounds for computing a feasible flow in a planar network, for finding a perfect matching in a planar bipartite graph, and for finding a maximum flow in a planar graph when the source and sink are not on the same face. We also give parallel and dynamic versions of these algorithms.

We describe a randomized CRCW PRAM algorithm that finds a minimum spanning forest of an n-vertex graph in O(log n) time and linear work. This shaves a factor of 2 log n off the best previous running time for a linear-work algorithm. The novelty in our approach is to divide the computation into two phases, the first of which finds only a partial solution. This idea has been used previously in parallel connected components algorithms. 1 Introduction We describe the first work-optimal minimum spanning forest (MSF) algorithm that runs in O(log n) time. The algorithm uses a random-sampling technique previously used by Karger, Klein, and Tarjan in a sequential linear-time algorithm and by Cole, Klein, and Tarjan in a parallel algorithm. These previous algorithms have the following form. Choose a random subset of edges, and recursively calculate the MSF of the sample graph, the graph consisting of the chosen edges. Use the recursively calculated minimum spanning forest to identify edges ...

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.Building on this result, Karger, Motwani, and Sudan gave an approximation algorithm for graph coloring that also involves solving a semidefinite program.Solving these semidefinite programs using known methods (ellipsoid, interiorpoint ), though polynomial-time, is quite expensive.We show how they can be approximately solved in ~(nm) time for graphs with n nodes and m edges.

We give the first efficient parallel algorithms for recognizing chordal graphs, finding a maximum clique and a maximum independent set in a chordal graph, finding an optimal coloring of a chordal graph, finding a breadth-first search tree and a depth-first search tree of a chordal graph, recognizing interval graphs, and testing interval graphs for isomorphism. The key to our results is an efficient parallel algorithm for finding a perfect elimination ordering.

We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons.

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 $\{i, j\}$ of nodes, an edgeconnectivity requirement $r_{ij}$. The goal is to find a minimum-cost network using the available links and satisfying the requirements. Our algorithm outputs a solution whose cost is within $2 \lceil {\log_{2}(r + 1)} \rceil $ of optimal, where r is the highest requirement value. In the course of proving the performance guarantee, we prove a combinatorial minmax approximate equality relating minimum-cost networks to maximum packings of certain kinds of cuts. As a consequence of the proof of this theorem, we obtain an approximation algorithm for optimally packing these cuts; we show that this algorithm has application to estimating the reliability of a probabilistic network.

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 with the source and sink on the same face. The previous best algorithms for these problems required\\Omega\\Gamma n p log n) time where n is the number of nodes in the input graph. For the case where negative edge-lengths are allowed, we give an algorithm requiring O(n 4=3 log nL) time, where L is the absolute value of the most negative length. Previous algorithms for shortest paths with negative edge-lengths required \\Omega\\Gamma n 3=2 ) time. Our shortest-path algorithm yields an O(n 4=3 log n)-time algorithm for finding a perfect matching in a planar bipartite graph. A similar improvement is obtained for maximum flow in a directed planar graph.

We present a randomized linear-time algorithm for finding a minimum spanning tree in a connected graph with edge weights. The algorithm is a modification of one proposed by Karger and uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum spanning tree. Our computational model is a unit-cost random-access machine with the restriction that the only operations allowed on edge weights are binary comparisons. 1 Introduction We consider the problem of finding a minimum spanning tree in a connected graph with real-valued edge weights. This problem has a long and rich history; the first fully realized algorithm was devised by Boruvka in the 1920's [3]. An informative survey paper by Graham and Hell [9] describes the history of the problem up to 1985. In the last two decades faster and faster algorithms were found, the fastest being an algorithm of Gabow, Galil, and Spencer [7] (see also [8]), with a running time of O(m log fi(m; n)) on a ...

This paper describes new algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities. These algorithms are much faster than algorithms discovered previously. Besides being an important problem in its own right, the uniform-capacity concurrent flow problem has many interesting applications. Leighton and Rao used uniform-capacity concurrent flow to find an approximately “sparsest cut” in a graph and thereby approximately solve a wide variety of graph problems, including minimum feedback arc set, minimum cut linear arrangement, and minimum area layout. However, their method appeared to be impractical as it required solving a large linear program. This paper shows that their method might be practical by giving an $O(m^2 \log m)$ expected-time randomized algorithm for their concurrent flow problem on an m-edge graph. Raghavan and Thompson used uniform-capacity concurrent flow to solve approximately a channel width minimization problem in very large scale integration. An $O(k^{{3 / 2}} (m + n\log n)$ expected-time randomized algorithm and an $O(k\min \{ n,k\} (m + n\log n)\log k)$ deterministic algorithm is given for this problem when the channel width is $\Omega (\log n)$, where k denotes the number of wires to be routed in an n-node, m-edge network.

We give an algorithm requiring polylog time and a linear number of processors to solve single-source shortest paths in directed planar graphs, bounded-genus graphs, and 2-dimensional overlap graphs. More generally, the algorithm works for any graph provided with a decomposition tree constructed using size-O(/spl radic/n polylog n) separators.>

We show how to obtain a work-efficient parallel algorithm for finding a planar separator. The algorithm requires O(rz’ ) time for any given positive constant e.

In this paper we show that, given a graph and parameters 6 and r, we can find either a K,,.minor or an edge-cut of size O(mT/6) whose removal yields components of weak diameter O(T-26); i.e., every pair of nodes in such a component are at distance 0(r26) in the original graph.Using this lemma, we improve the best known bounds for the rein-cut max-flow ratio for mukicommodity flows in graphs with forbidden small minors.In general graphs, it was known that the ratio is O(log k) for the uniform-demand case (the case where there is a unit-demand commodity between every pair of nodes), and that the ratio is 0(log2 k) for arbitrary demands, where k is the number of commodities.In this paper we show that for graphs excluding any fixed graph as a minor (e.g.planar graphs or boundedgenus graphs), the ratio is O(1) for the uniform-demand case and O(log k) for the arbitrary demand case.For such graphs, our method yields rein-ratio cut approximation algorithms with performance bounds that match the above ratios.Computation of such cuts is a basic step for a variety of approximation algorithms for NP-complete problems.

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 solutions to the planar circulation problem and with “consistent” potential functions in the dual graph are shown. It is also shown that the set of integral circulations in a planar graph very naturally forms a distributive lattice whose maximum corresponds to the shortest path tree in the dual graph. Further characterized is the lattice in terms of unidirectional cycles with respect to a particular face called the root face. It is shown how to compactly encode the entire lattice and it is also shown that the set of solutions to the min-cost flow problem forms a sublattice in the presented lattice.

We give a randomized parallel algorithm for approximate shortest path computation in an undirected weighted graph. The algorithm is based on a technique used by Ullman and Yannakakis in a parallel algorithm for breadth-first search. It has application, e.g., in approximate solution of multicommodity flow problems with unit capacities. We also show how to adapt the algorithm to perform better for planar graphs.

Article When trees collide: an approximation algorithm for the generalized Steiner problem on networks Share on Authors: Ajit Agrawal Brown Univ., Providence, RI Brown Univ., Providence, RIView Profile , Philip Klein Brown Univ., Providence, RI Brown Univ., Providence, RIView Profile , R. Ravi Brown Univ., Providence, RI Brown Univ., Providence, RIView Profile Authors Info & Claims STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of ComputingJanuary 1991 Pages 134–144https://doi.org/10.1145/103418.103437Online:03 January 1991Publication History 47citation861DownloadsMetricsTotal Citations47Total Downloads861Last 12 Months16Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The first approximate max-flow-min-cut theorem for general multicommodity flow is proved. It is used to obtain approximation algorithms for minimum deletion of clauses of a 2-CNF identical to formula, via minimization problems, and other problems. Also presented are approximation algorithms for chordalization of a graph and for register sufficiency that are based on undirected and directed node separators.>

Currently, there is a significant gap between the best sequential and parallel complexities of many fundamental problems related to digraph reachability.This complexity bottleneck essentially reflects a seemingly unavoidable reliance on transitive closure techniques in parallel algorithms for digraph reachability.To pinpoint the nature of the bottleneck, we de* velop a collection of polylog-time reductions among reachability problems.These reductions use only linear processors and work for general graphs.Furthermore, for planar digraphs, we give polylog-time algorithms for the following problems: (1) directed ear decomposition, (2) topological ordering, (3) digraph reachability, (4) descendent counting, and (5) depth-first search.These algorithms use only linear processors and therefore reduce the complexity to within a polylog factor of optimal.

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 algorithms.Besides being an important problem in its own right, the concurrent flow problem has many interesting applications.Leighton and Rao used concurrent flow to find an approximately "sparsest cut" in a graph, and thereby approximately solve a wide variety of graph problems, including minimum feedback arc set, minimum cut linear arrangement, and minimum area layout.We show that their method might be practical by giving an O(m~logm) expected-time randomized algorithm for their concurrent flow problem on an m-edge graph.l~aghavan and Thompson used concurrent flow to approximately solve a channel width minimization problem in VLSI.We give an O(k3/2(m+n log n)) expectedtime randomized algorithm and an O(k min{n, k}(m + n log n) log k) deterministic algorithm for this problem when the channel width is O(logn), where k denotes the number of wires to be routed in an n-node, m-edge network,

The author gives efficient parallel algorithms for recognizing chordal graphs, finding a maximum clique and a maximum independent set in a chordal graph, finding an optimal coloring of a chordal graph, finding a breadth-first search tree and a depth-first search tree of a chordal graph, recognizing interval graphs, and testing interval graphs for isomorphism. The key to the results is an efficient parallel algorithm for finding a perfect elimination ordering.>

We give an algorithm for accepting a deterministic context-free language on the P-RAM, an exclusive-write, concurrent-read model of parallel computation. Whereas on inputs of length n, a deterministic push-down automaton will use time linear in n, our algorithm runs in time $O(\log n)$ on $n^3 $ processors. The algorithm is easily generalized to permit parallel simulation of any deterministic auxiliary pushdown automaton that uses space $s(n) \geqq \log n$ and time $2^{O(s(n))} $. The simulation runs in time $O(s(n))$ on $2^{O(s(n))} $ processors, and is nearly optimal, since we observe that any language accepted by a P-RAM in time $T(n)$ is accepted by a deterministic auxiliary pushdown automaton in space $T(n)$ and time $2^{O(T(n)^2 )} $.

We describe a parallel algorithm for testing a graph for planarity, and for finding an embedding of a planar graph. For a graph on n vertices, the algorithm runs in O(log2 n) steps on n processors of a parallel RAM. The previous best algorithm for planarity testing in parallel polylog time ([Ja'Ja' and Simon, 82]) used a reduction to solving linear systems, and hence required Ω(n2..49...) processors by known methods, whereas our processor bounds are within a polylog factor of optimal. The most significant aspect of our parallel algorithms is the use of a sophisticated data structure for representing sets of embeddings, the PQ-tree of [Booth and Lueker, 76]. Previously no parallel algorithms for PQ-trees were known. We have efficient parallel algorithms for manipulating PQ-trees, which we use in our planarity algorithm.