Solving problems on graphs dynamically calls for algorithms to function under repeated modifications to the graph and to be more efficient than solving the problem for the whole graph from scratch after each modificat...
详细信息
Solving problems on graphs dynamically calls for algorithms to function under repeated modifications to the graph and to be more efficient than solving the problem for the whole graph from scratch after each modification. dynamicalgorithms have been considered for several graph properties, for example connectivity, shortest paths and graph recognition. In this paper we present fully dynamic algorithms for the recognition of threshold graphs and chain graphs, which are optimal in the sense that the costs per modification are linear in the number of modified edges. Furthermore, our algorithms also consider the addition and deletion of sets of vertices as well as edges. In the negative case, i.e., where the graph is not a threshold graph or chain graph anymore, our algorithms return a certificate of constant size. Additionally, we present optimal fully dynamic algorithms for the Hamiltonian cycle problem and the Hamiltonian path problem on threshold and chain graphs which return a vertex cutset as certificate for the non-existence of such a path or cycle in the negative case.
Maximizing monotone submodular functions under a matroid constraint is a classic algorithmic problem with multiple applications in data mining and machine learning. We study this significant problem in the fully dynam...
详细信息
Maximizing monotone submodular functions under a matroid constraint is a classic algorithmic problem with multiple applications in data mining and machine learning. We study this significant problem in the fullydynamic setting, where elements can be both inserted and deleted in real-time. Our main result is a randomized algorithm that maintains an efficient data structure with an O ( :Y2 ) amortized update time (in the number of insertions and deletions) and yields a (4 + O ( pound ))-approximate solution with respect to the dynamic optimum, where k is the rank of the matroid.
In this paper, we revisit the split decomposition of graphs and give new combinatorial and algorithmic results for the class of totally decomposable graphs, also known as the distance hereditary graphs, and for two no...
详细信息
In this paper, we revisit the split decomposition of graphs and give new combinatorial and algorithmic results for the class of totally decomposable graphs, also known as the distance hereditary graphs, and for two non-trivial subclasses, namely the cographs and the 3-leaf power graphs. Precisely, we give structural and incremental characterizations, leading to optimal fullydynamic recognition algorithms for vertex and edge modifications, for each of these classes. These results rely on the new combinatorial framework of graph-labelled trees used to represent the split decomposition of general graphs (and also the modular decomposition). The point of the paper is to use bijections between the aforementioned graph classes and graph-labelled trees whose nodes are labelled by cliques and stars. We mention that this bijective viewpoint yields directly an intersection model for the class of distance hereditary graphs. (C) 2012 Published by Elsevier B.V.
We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fullydynamic graph G = (V, E), with vertical bar V vertical bar = n and vertical bar E ver...
详细信息
We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fullydynamic graph G = (V, E), with vertical bar V vertical bar = n and vertical bar E vertical bar = m, in o(root m) time per update. In particular, for minimum vertex cover, we provide deterministic data structures for maintaining a (2+epsilon) approximation in O(log n/epsilon(2)) amortized time per update. For maximum matching, we show how to maintain a (3+epsilon) approximation in O(min(root n/epsilon m(1/3)/epsilon(2)) amortized time per update and a (4 + epsilon) approximation in O(m1/3/epsilon(2)) worst-case time per update. Our data structure for fullydynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld [in 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, pp. 457-464].
In this paper, we revisit the split decomposition of graphs and give new combinatorial and algorithmic results for the class of totally decomposable graphs, also known as the distance hereditary graphs, and for two no...
详细信息
In this paper, we revisit the split decomposition of graphs and give new combinatorial and algorithmic results for the class of totally decomposable graphs, also known as the distance hereditary graphs, and for two non-trivial subclasses, namely the cographs and the 3-leaf power graphs. Precisely, we give structural and incremental characterizations, leading to optimal fullydynamic recognition algorithms for vertex and edge modifications, for each of these classes. These results rely on the new combinatorial framework of graph-labelled trees used to represent the split decomposition of general graphs (and also the modular decomposition). The point of the paper is to use bijections between the aforementioned graph classes and graph-labelled trees whose nodes are labelled by cliques and stars. We mention that this bijective viewpoint yields directly an intersection model for the class of distance hereditary graphs. (C) 2012 Published by Elsevier B.V.
We consider the dynamic recognition problem for the class of P-4-sparse graphs: the objective is to handle edge/vertex additions and deletions, to recognize if each such modification yields a P-4-sparse graph, and if ...
详细信息
ISBN:
(纸本)3540483810
We consider the dynamic recognition problem for the class of P-4-sparse graphs: the objective is to handle edge/vertex additions and deletions, to recognize if each such modification yields a P-4-sparse graph, and if yes, to update a representation of the graph. Our approach relies on maintaining the modular decomposition tree of the graph, which we use for solving the recognition problem. We establish conditions for each modification to yield a P-4-sparse graph and obtain a fullydynamic recognition algorithm which handles edge modifications in 0(l) time and vertex modifications in O(d) time for a vertex of degree d. Thus, our algorithm implies an optimal edges-only dynamic algorithm and a new optimal incremental algorithm for P4-sparse graphs. Moreover, by maintaining the children of each node of the modular decomposition tree in a binomial heap, we can handle vertex deletions in O(log n) time, at the expense of needing O(log n) time for each edge modification and 0(d log n) time for the addition of a vertex adjacent to d vertices.
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 fullydynamic 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.
暂无评论