206562722
Dominating Sets in Planar Graphs
Motivated by an application to unstructured multigrid calculations, we consider the problem of asymptotically minimizing the size of dominating sets in triangulated planar graphs. Specifically, we wish to find the smallestesuch that, fornsufficiently large, everyn-vertex planar graph contains a dominating set of size at mosten.We prove that 1/4<e<1/3, and we conjecture thate=1/4.For triangulated discs we obtain a tight bound ofe=1/3.The upper bound proof yields a linear-time algorithm for finding an(n/3)-size dominating set.
1829912
The Planar Hamiltonian Circuit Problem is NP-Complete
We consider the problem of determining whether a planar, cubic, triply-connected graph G has a Hamiltonian circuit. We show that this problem is NP-complete. Hence the Hamiltonian circuit problem for this class of graphs, or any larger class containing all such graphs, is probably computationally intractable.
9258095
Intersection graphs of curves in the plane
Abstract Let V be a set of curves in the plane. The corresponding intersection graph has V as the set of vertices, and two vertices are connected by an edge if and only if the two corresponding curves intersect in the plane. It is shown that the set of intersection graphs of curves in the plane is a proper subset of the set of all undirected graphs. Furthermore, the set of intersection graphs of straight line-segments is a proper subset of the set of the intersection graphs of curves in the plane. Finally, it is shown that for every k ≥ 3, the problem of determining whether an intersection graph of straight line-segments is k -colorable is NP -complete.
44984412
A Note on Finding the Bridges of a Graph
ly, algorithms havg been developed which 4Irst search to test various connectivity proof gzpks efficiently. Examples include algod9 find the wnnected, biconnected, and tricon; components of an undirected graph [l-3], the strongi> connected components 123 and domors [4] of a =dLected graph. Depth-first search is n0t &ways necessary for testing connectivity properthese efkiently, however. This note presents ent algorithm which uses any search method to And all the bridges of a graph. A gmph C = Cv,, e) is a set of vertices39 and a set of edges ~5. The edges are either unordered pairs (v, w) or distinc; vertices (the graph Is tial+eccieu~ or ordered pain (P? tr?ll) of distinct vertices (the graph isdkected). We denote the number of vertices by Vand the nurtther of edges by E. Graph G, = fc191,& 1) is a subgraph w’ G if”“? (vi, Q), t c cp’ and e I G.lf. A sequence of edges 5, vg), l *, fv,l, vn) is a puth from vl Co . A path is &zpl’e if all its vertices are distinct. There path of no edges from any vertex to itself. An un&tied graph is csnmt ted if there is a path between every pak of vertices. If there is a path from a vertex ~16flz vertex w in G but every path frt?m u to w con*&% edge e, then e is said to be a brki,{e of G. An undirected graph is Zridge-cunnected if i:: is connected and has no bridges. The connected (bridge-connected) components of a graph are its maxin% connected (bridgeconnected) szbgraphs.
11724969
Finding a Maximum Independent Set
We present an algorithm which finds a maximum independent set in an n-vertex graph in 0($2^{n/3}$) time. The algorithm can thus handle graphs roughly three times as large as could be analyzed using a naive algorithm.
31445898
Enumeration of the Elementary Circuits of a Directed Graph
An algorithm to enumerate all the elementary circuits of a directed graph is presented. The algorithm uses back-tracking with lookahead to avoid unnecessary work, and it has a time bound of $O ((V+E)(C+1))$ when applied to a graph with $V$ vertices, $E$ edges, and $C$ elementary circuits. Keywords: Algorithm, circuit, cycle, graph
10887766
Fully persistent lists with catenation
This paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. This problem arises in the implementation of list-based and functional programming languages. A solution is proposed requiring constant time and space for each stack operation except catenation, which requires O(log log k) time and space. Here k is the number of stack operations done before the catenation. All the resource bounds are amortized over the sequence of operations.
7483054
A Linear-Time Algorithm for a Special Case of Disjoint Set Union
This paper presents a linear-time algorithm for the special case of the disjoint set union problem in which the structure of the unions (defined by a “union tree”) is known in advance. The algorithm executes an intermixed sequence of m union and find operations on n elements in O(m+n) time and O(n) space. This is a slight but theoretically significant improvement over the fastest known algorithm for the general problem, which runs in O(mα(m+n, n)+n) time and O(n) space, where a is a functional inverse of Ackermann's function. Used as a subroutine, the algorithm gives similar improvements in the efficiency of algorithms for solving several other problems, including two-processor scheduling, matching on convex graphs, finding nearest common ancestors off-line, testing a flow graph for reducibility, and finding two disjoint directed spanning trees. The algorithm obtains its efficiency by combining the fast algorithm for the general problem with table look-up on small sets, and requires a random access machine for its implementation. The algorithm extends to the case in which single-node additions to the union tree are allowed. The extended algorithm is useful in finding maximum cardinality matchings in nonbipartite graphs.
18699794
Almost-optimum speed-ups of algorithms for bipartite matching and related problems
We present algorithms for matching and related problems that run on an EREW PRAM with <italic>p</italic> processors. Given is a bipartite graph <italic>G</italic> with <italic>n</italic> vertices, <italic>m</italic> edges, and integral edge costs at most <italic>N</italic> in magnitude. We give an algorithm for the assignment problem (minimum cost perfect bipartite matching) that runs in <italic>&Ogr;</italic>(√<italic>nm</italic> log (<italic>nN</italic>)(log(2<italic>p</italic>))/<italic>p</italic>) time and <italic>&Ogr;</italic>(<italic>m</italic>) space, for <italic>p</italic> ≤ <italic>m</italic>/(√<italic>n</italic>log<supscrpt>2</supscrpt><italic>n</italic>). For <italic>p</italic> = 1 this improves the best known sequential algorithm, and is within a factor of log (<italic>nN</italic>) of the best known bound for the problem without costs (maximum cardinality matching). For <italic>p</italic> > 1 the time is within a factor of log <italic>p</italic> of optimum speed-up. Extensions include an algorithm for maximum cardinality bipartite matching with slightly better processor bounds, and similar results for bipartite degree-constrained subgraph problems (with and without costs). Our ideas also extend to general graph matching problems.
52152408
A new approach to the maximum-flow problem
All previously known efficient maximum-flow algorithms work by finding augmenting paths, either one path at a time (as in the original Ford and Fulkerson algorithm) or all shortest-length augmenting paths at once (using the layered network approach of Dinic). An alternative method based on the <italic>preflow</italic> concept of Karzanov is introduced. A preflow is like a flow, except that the total amount flowing into a vertex is allowed to exceed the total amount flowing out. The method maintains a preflow in the original network and pushes local flow excess toward the sink along what are estimated to be shortest paths. The algorithm and its analysis are simple and intuitive, yet the algorithm runs as fast as any other known method on dense graphs, achieving an <italic>O</italic>(<italic>n</italic><supscrpt>3</supscrpt>) time bound on an <italic>n</italic>-vertex graph. By incorporating the dynamic tree data structure of Sleator and Tarjan, we obtain a version of the algorithm running in <italic>O</italic>(<italic>nm</italic> log(<italic>n</italic><supscrpt>2</supscrpt>/<italic>m</italic>)) time on an <italic>n</italic>-vertex, <italic>m</italic>-edge graph. This is as fast as any known method for any graph density and faster on graphs of moderate density. The algorithm also admits efficient distributed and parallel implementations. A parallel implementation running in <italic>O</italic>(<italic>n</italic><supscrpt>2</supscrpt>log <italic>n</italic>) time using <italic>n</italic> processors and <italic>O</italic>(<italic>m</italic>) space is obtained. This time bound matches that of the Shiloach-Vishkin algorithm, which also uses <italic>n</italic> processors but requires <italic>O</italic>(<italic>n</italic><supscrpt>2</supscrpt>) space.