In this paper we study the problem of recognizing and representing dynamically changing proper interval graphs. The input to the problem consists of a series of modifications to be performed on a graph, where a modi c...
详细信息
In this paper we study the problem of recognizing and representing dynamically changing proper interval graphs. The input to the problem consists of a series of modifications to be performed on a graph, where a modi cation can be a deletion or an addition of a vertex or an edge. The objective is to maintain a representation of the graph as long as it remains a proper interval graph, and to detect when it ceases to be so. The representation should enable one to efficiently construct a realization of the graph by an inclusion-free family of intervals. This problem has important applications in physical mapping of DNA. We give a near-optimal fully dynamic algorithm for this problem. It operates in O(log n) worst-case time per edge insertion or deletion. We prove a close lower bound of Omega (log n/(log log n + log b)) amortized time per operation in the cell probe model with word-size b. We also construct optimal incremental and decremental algorithms for the problem, which handle each edge operation in O(1) time. As a byproduct of our algorithm, we solve in O ( log n) worst-case time the problem of maintaining connectivity in a dynamically changing proper interval graph.
Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n, N, and W be the node count, the largest edge weight, and the total weight of G. Let k (x, y) be log x/log(x(2)/y...
详细信息
Let G be a bipartite graph with positive integer weights on the edges and without isolated nodes. Let n, N, and W be the node count, the largest edge weight, and the total weight of G. Let k (x, y) be log x/log(x(2)/y). We present a new decomposition theorem for maximum weight bipartite matchings and use it to design an O (n rootW/k(n,W/N))-time algorithm for computing a maximum weight matching of G. This algorithm bridges a long-standing gap between the best known time complexity of computing a maximum weight matching and that of computing a maximum cardinality matching. Given G and a maximum weight matching of G, we can further compute the weight of a maximum weight matching of G-{u} for all nodes u in O(W) time.
Linear time algorithms are presented which generate the Voronoi tessellation from a Delaunay tessellation and vice versa when the tessellations of convex polygons and triangles are stored as edge-adjacent undirected g...
详细信息
Linear time algorithms are presented which generate the Voronoi tessellation from a Delaunay tessellation and vice versa when the tessellations of convex polygons and triangles are stored as edge-adjacent undirected graphs. These two geometric algorithms lead naturally to two further linear and quadratic graph algorithms for determining the minimal simple cycles or regions in both triangular and regular-3 undirected planar graphs. (C) 2001 Elsevier Science Ltd. All rights reserved.
We present a derivation of Dijkstra's shortest path algorithm [Numer. Math. 1 (1959) 83]. We view the problem as computation of a "greatest solution" of a set of equations. A UNITY-style computation [Cha...
详细信息
We present a derivation of Dijkstra's shortest path algorithm [Numer. Math. 1 (1959) 83]. We view the problem as computation of a "greatest solution" of a set of equations. A UNITY-style computation [Chandy and Misra, Parallel Program Design: A Foundation, 1988] is then prescribed whose implementation results in Dijkstra's algorithm. (C) 2001 Elsevier Science B.V. All rights reserved.
Let P-G(r, s) denote a shortest path between two nodes r and s in an undirected graph G = (V, E) such that /V/ = n and /E/ = m and with a positive real length w(e) associated with any e E E. In this paper we focus on ...
详细信息
Let P-G(r, s) denote a shortest path between two nodes r and s in an undirected graph G = (V, E) such that /V/ = n and /E/ = m and with a positive real length w(e) associated with any e E E. In this paper we focus on the problem of finding an edge e* is an element of P-G(r, s) whose removal is such that the length of PG-e*(r, s) is maximum, where G - e* = (V, E \ {e*}). Such an edge is known as the most vital edge of the path P-G(r, s). We will show that this problem can be solved in O(*** (m, n)) time, where ct is the functional inverse of the Ackermann function, thus improving on the previous O(m + n log n) time bound. (C) 2001 Elsevier Science B.V. All rights reserved.
In this paper a parallel algorithm is given that, given a graph G = (V, E), decides whether G is a series parallel graph, and, if so, builds a decomposition tree for G of series and parallel composition rules. The alg...
详细信息
In this paper a parallel algorithm is given that, given a graph G = (V, E), decides whether G is a series parallel graph, and, if so, builds a decomposition tree for G of series and parallel composition rules. The algorithm uses O (log\E\log*\E\) time and O(\E\) operations on an EREW PRAM, and O (log \E\) time and O(\E\) operations on a CRCW PRAM. The results hold for undirected as well as for directed graphs. algorithms with the same resource bounds are described for the recognition of graphs of treewidth two, and for constructing tree decompositions of treewidth two. Hence efficient parallel algorithms can be found for a large number of graph problems on series parallel graphs and graphs with treewidth two. These include many well-known problems like all problems that can be stated in monadic second-order logic.
An algorithm is proposed for extracting regulatory signals from DNA sequences. The algorithm complexity is nearly quadratic. The results of testing the algorithm on artificial and natural sequences are presented.
An algorithm is proposed for extracting regulatory signals from DNA sequences. The algorithm complexity is nearly quadratic. The results of testing the algorithm on artificial and natural sequences are presented.
In this paper, we consider the r-dominating set problem on graphs which can be generated from the one-vertex graph by a finite number of homogeneous extensions and by attaching pendant vertices. We show that for such ...
详细信息
In this paper, we consider the r-dominating set problem on graphs which can be generated from the one-vertex graph by a finite number of homogeneous extensions and by attaching pendant vertices. We show that for such graphs a minimum cardinality r-dominating set can be computed in O(\V\ \E\) time;for distance-hereditary graphs-a proper subclass-we even get a linear time algorithm. Furthermore, since these graph classes are closed under adding false twins, a total dominating set can be computed in the same time bound. (C) 2001 John Wiley & Sons, Inc.
In an edge modification problem one has to change the edge set of a given graph as little as possible so as to satisfy a certain property. We prove the NP-hardness of a variety of edge modification problems with respe...
详细信息
In an edge modification problem one has to change the edge set of a given graph as little as possible so as to satisfy a certain property. We prove the NP-hardness of a variety of edge modification problems with respect to some well-studied classes of graphs. These include perfect, chordal, chain, comparability, split and asteroidal triple free. We show that some of these problems become polynomial when the input graph has bounded degree. We also give a general constant factor approximation algorithm for deletion and editing problems on bounded degree graphs with respect to properties that can be characterized by a finite set of forbidden induced subgraphs. (C) 2001 Elsevier Science B.V. All rights reserved.
In this paper we provide SAT-solving procedures that use the idea of decomposition together with the heuristic of solving the most constrained subproblem first. We present two approaches. We provide an algorithm to fi...
详细信息
In this paper we provide SAT-solving procedures that use the idea of decomposition together with the heuristic of solving the most constrained subproblem first. We present two approaches. We provide an algorithm to find the most constrained subproblem of a propositional SAT problem in polynomial time. We use this algorithm iteratively to decompose a SAT problem into partitions. We also provide a polynomial-time algorithm that uses the idea of minimum vertex separators iteratively to provide different decompositions. We show how to solve SAT problems, using these algorithms to emphasize solving the most constrained subproblem first.
暂无评论