Recently lexicographic breadth first search (LexBFS) has been shown to be a very powerful tool for the development of linear time, easily implementable recognition algorithms for various families of graphs. In this pa...
详细信息
Recently lexicographic breadth first search (LexBFS) has been shown to be a very powerful tool for the development of linear time, easily implementable recognition algorithms for various families of graphs. In this paper, we add to this work by producing a simple two LexBFS sweep algorithm to recognize the family of cographs. This algorithm extends to other related graph families such as P-4-reducible, P-4-sparse, and distance hereditary. It is an open question whether our cograph recognition algorithm can be extended to a similarly easy algorithm for modular decomposition.
As part of the efforts to understand the intricacies of the k-colorability problem, different distributions over k-colorable graphs have been analyzed. While the problem is notoriously hard (not even reasonably approx...
详细信息
As part of the efforts to understand the intricacies of the k-colorability problem, different distributions over k-colorable graphs have been analyzed. While the problem is notoriously hard (not even reasonably approximable) in the worst case, the average case (with respect to such distributions) often turns out to be "easy". Semi-random models mediate between these two extremes and are more suitable to imitate "real-life" instances than purely random models. In this work we consider semi-random variants of the planted k-colorability distribution. This continues a line of research pursued by Coja-Oghlan, and by Krivelevich and Vilenchik. Our aim is to study a more general semi-random framework than those suggested so far. On the one hand we show that previous algorithmic techniques extend to our more general semi-random setting: on the other hand we give a hardness result, proving that a closely related semi-random model is intractable. Thus we provide some indication about which properties of the input distribution make the k-colorability problem hard. (C) 2008 Elsevier B.V. All rights reserved.
We consider the problem of preprocessing an edge-weighted directed graph G to answer queries that ask for the length and first hop of a shortest path from any given vertex x to any given vertex y avoiding any given ve...
详细信息
We consider the problem of preprocessing an edge-weighted directed graph G to answer queries that ask for the length and first hop of a shortest path from any given vertex x to any given vertex y avoiding any given vertex or edge. As a natural application, this problem models routing in networks subject to node or link failures. We describe a deterministic oracle with constant query time for this problem that uses O(n(2) log n) space, where n is the number of vertices in G. The construction time for our oracle is O(mn(2) + n(3) log n). However, if one is willing to settle for Theta(n(2.5)) space, we can improve the preprocessing time to O(mn(1.5) + n(2.5) log n) while maintaining the constant query time. Our algorithms can find the shortest path avoiding a failed node or link in time proportional to the length of the path.
We describe a polynomial time algorithm to find a minimum weight feedback vertex set, or equivalently, a maximum weight induced forest, in a circle graph. The circle graphs are the overlap graphs of intervals on a lin...
详细信息
We describe a polynomial time algorithm to find a minimum weight feedback vertex set, or equivalently, a maximum weight induced forest, in a circle graph. The circle graphs are the overlap graphs of intervals on a line. (C) 2007 Elsevier B.V. All rights reserved.
We present an O(n(3)(log log n/log n)(5/4)) time algorithm for all pairs shortest paths. This algorithm improves on the best previous result of O(n(3)/log n) time.
We present an O(n(3)(log log n/log n)(5/4)) time algorithm for all pairs shortest paths. This algorithm improves on the best previous result of O(n(3)/log n) time.
We develop a combinatorial polynomial-time algorithm to make a (k-1)-connected digraph k-connected by adding a minimum number of new edges. (c) 2008 Elsevier B.V. All rights reserved.
We develop a combinatorial polynomial-time algorithm to make a (k-1)-connected digraph k-connected by adding a minimum number of new edges. (c) 2008 Elsevier B.V. All rights reserved.
Given a forest F = (V, E) and a positive integer D, we consider the problem of finding a minimum number of new edges E' such that in the augmented graph H = (V, E boolean OR E') any pair of vertices can be con...
详细信息
Given a forest F = (V, E) and a positive integer D, we consider the problem of finding a minimum number of new edges E' such that in the augmented graph H = (V, E boolean OR E') any pair of vertices can be connected by two vertex-disjoint paths of length <= D. We show that this problem and some of its variants are NP-hard, and we present approximation algorithms with worst-case bounds 6 and 4. These algorithms can be implemented in O(vertical bar V vertical bar log vertical bar V vertical bar a) time. (c) 2008 Elsevier B.V. All rights reserved.
The DEGREE-Delta CLOSEST PHYLOGENETIC kTH ROOT PROBLEM (Delta CPRk) is the problem of finding a (phylogenetic) tree T from a given graph G = ( V, E) such that ( 1) the degree of each internal node in T is at least 3 a...
详细信息
The DEGREE-Delta CLOSEST PHYLOGENETIC kTH ROOT PROBLEM (Delta CPRk) is the problem of finding a (phylogenetic) tree T from a given graph G = ( V, E) such that ( 1) the degree of each internal node in T is at least 3 and at most., ( 2) the external nodes (i.e. leaves) of T are exactly the elements of V, and ( 3) the number of disagreements, i.e., | E circle plus{{u, v} : u, v are leaves of T and d(T) ( u, v) <= k}|, is minimized, where d(T) ( u, v) denotes the distance between u and v in tree T. This problem arises from theoretical studies in evolutionary biology and generalizes several important combinatorial optimization problems such as the maximum matching problem. Unfortunately, it is known to be NP-hard for all fixed constants Delta, k such that either both Delta >= 3 and k >= 3, or Delta > 3 and k = 2. This paper presents a polynomial-time 8-approximation algorithm for Delta CPR2 for any fixed Delta > 3, a quadratic-time 12-approximation algorithm for 3CPR(3), and a polynomial-time approximation scheme for the maximization version of Delta CPRk for any fixed. and k.
st-orientations (st-numberings) or bipolar orientations of undirected graphs are central to many graph algorithms and applications. Several algorithms have been proposed in the past to compute an st-orientation of a b...
详细信息
st-orientations (st-numberings) or bipolar orientations of undirected graphs are central to many graph algorithms and applications. Several algorithms have been proposed in the past to compute an st-orientation of a biconnected graph. In this paper, we present new algorithms that compute such orientations with certain (parameterized) characteristics in the final st-oriented graph, such as the length of the longest path. This work has many applications, including graph Drawing and Network Routing, where the length of the longest path is vital in deciding certain features of the final solution. This work applies to other difficult problems as well, such as graph coloring and of course longest path. We present extended theoretical and experimental results which show that our technique is efficient and performs well in practice. (C) 2008 Elsevier B.V. All rights reserved.
Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a g...
详细信息
Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O* (2(n-z)), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O*(2(n/2)). Another implication is an algorithm for general graphs whose running time is O(1.7088(n)). (C) 2008 Elsevier B.V. All rights reserved.
暂无评论