We introduce the decision problem BICOLORED INDEPENDENT SET which generalizes the well-known NP-complete graph problem INDEPENDENT SET. We present an O(1.2691(n)) time algorithm solving its counting analogue #BICOLORE...
详细信息
We introduce the decision problem BICOLORED INDEPENDENT SET which generalizes the well-known NP-complete graph problem INDEPENDENT SET. We present an O(1.2691(n)) time algorithm solving its counting analogue #BICOLORED INDEPENDENT SET. We show how to use this algorithm to establish algorithms solving biclique counting problems and provide an O(1.2691(n)) time algorithm solving *BIPARTITE BICLIQUE and an O(1.6107(n)) time algorithm solving #NON-INDUCED BICLIQUE. (C) 2012 Elsevier B.V. All rights reserved.
We introduce a generic approach for counting subgraphs in a graph. The main idea is to relate counting subgraphs to counting graph homomorphisms. This approach provides new algorithms and unifies several well-known re...
详细信息
We introduce a generic approach for counting subgraphs in a graph. The main idea is to relate counting subgraphs to counting graph homomorphisms. This approach provides new algorithms and unifies several well-known results in algorithms and combinatories, including the recent algorithm of Bjorklund, Husfeldt, and Koivisto for computing the chromatic polynomial, the classical algorithm of Kohn et al. for counting Hamiltonian cycles, Ryser's formula for counting perfect matchings of a bipartite graph, and color-coding-based algorithms of Alon, Yuster, and Zwick. By combining our method with known combinatorial bounds, ideas from succinct data structures, partition functions, and the color coding technique, we obtain the following new results. The number of optimal bandwidth permutations of a graph on n vertices excluding a fixed graph as a minor can be computed in time 2(n+o(n)), in particular, in time O(2(n)n(3)) for trees and in time 2(n+O(root n)) for planar graphs. Counting all maximum planar subgraphs, subgraphs of bounded genus, or more generally subgraphs excluding a fixed graph M as a minor can be done in 2(O(n)) time. Counting all subtrees with a given maximum degree ( a generalization of counting Hamiltonian paths) of a given graph can be done in time 2(O(n)). A generalization of Ryser's formula is, Let G be a graph with an independent set of size l. Then the number of perfect matchings in G can be found in time O(2(n)(n-l)(3)). Let H be a graph class excluding a fixed graph M as a minor. Then the maximum number of vertex disjoint subgraphs from H in a graph G on n vertices can be found in time 2(O(n)). In order to show this, we prove that there exists a constant c(M) depending only on M such that the number of nonisomorphic n-vertex graphs in H is at most c(M)(n). Let F be a k-vertex graph of treewidth t and let G be an n-vertex graph. A subgraph of G isomorphic to F (if one exists) can be found in O(4.32(k).k.t.n(t+1)) expected time using O(log k.n(t+1)) s
Hypergraph width measures are important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exactexponential algorithm for a large variety of these measures. As a consequence, ...
详细信息
Hypergraph width measures are important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exactexponential algorithm for a large variety of these measures. As a consequence, we obtain algorithms which, for a hypergraph H on n vertices and m hyperedges, compute its generalized hypertree-width in time O*(2(n)) and its fractional hypertree-width in time O(1.734601(n) .m)(3). (C) 2011 Elsevier B.V. All rights reserved.
In this paper we present branching algorithms for infinite classes of problems. The novelty in the design and analysis of our branching algorithms lies in the fact that the weights are redistributed over the graph by ...
详细信息
In this paper we present branching algorithms for infinite classes of problems. The novelty in the design and analysis of our branching algorithms lies in the fact that the weights are redistributed over the graph by the algorithms. Our particular setting to make this idea work is a combination of a branching approach with a recharging mechanism. We call it Branch & Recharge. To demonstrate this approach we consider a generalized domination problem. Let sigma and I +/- be two nonempty sets of nonnegative integers. A vertex subset SaS dagger V of an undirected graph G=(V(G),E(G)) is called a (sigma,I +/-)-dominating set of G if |N(v)a (c) S|a sigma for all vaS and |N(v)a (c) S|aI +/- for all vaVa-S. This notion generalizes many domination-type graph invariants. We present Branch & Recharge algorithms enumerating all (sigma,I +/-)-dominating sets of an input graph G in time O (*)(c (n) ) for some c < 2, if sigma is successor-free, i.e., it does not contain two consecutive integers, and either both sigma and I +/- are finite, or one of them is finite and sigma a (c) I +/-=a.... Our algorithm implies a non trivial upper bound of O (*)(c (n) ) on the number of (sigma,I +/-)-dominating sets in an n-vertex graph under the above conditions on sigma and I +/-.
We prove that the rank-width of an n-vertex graph can be computed exactly in time O(2(n)n(3) log(2) n log log n). To improve over a trivial O(3(n) log n)-time algorithm, we develop a general framework for decompositio...
详细信息
We prove that the rank-width of an n-vertex graph can be computed exactly in time O(2(n)n(3) log(2) n log log n). To improve over a trivial O(3(n) log n)-time algorithm, we develop a general framework for decompositions on which an optimal decomposition can be Computed efficiently. This framework may be used for other width parameters, including the branch-width of matroids and the carving-width of graphs. (C) 2009 Elsevier B.V. All rights reserved.
In this paper we propose an O(1.0892(n))algorithm solving the Maximum Independent Set problem for graphs with maximum degree 3 improving the previously best upper bound of O(1.0977(n)). A useful secondary effect of th...
详细信息
In this paper we propose an O(1.0892(n))algorithm solving the Maximum Independent Set problem for graphs with maximum degree 3 improving the previously best upper bound of O(1.0977(n)). A useful secondary effect of the proposed algorithm is that being applied to 2k kernel, it improves the upper bound on the parameterized complexity of the Vertex Cover problem for graphs with maximum degree 3 (VC-3). In particular, the new upper bound for the VC-3 problem is O(1.1864(k) + n), improving the previously best upper bound of O(k(2) * 1.194(k) + n). The presented results have a methodological interest because, to the best of our knowledge, this is the first time when a new parameterized upper bound is obtained through design and analysis of an exactexponential algorithm. (C) 2008 Elsevier B.V. All rights reserved.
We provide an algorithm listing all minimal dominating sets of a graph on n vertices in time O(1.7159(n)). This result can be seen as an algorithmic proof of the fact that the number of minimal dominating sets in a gr...
详细信息
We provide an algorithm listing all minimal dominating sets of a graph on n vertices in time O(1.7159(n)). This result can be seen as an algorithmic proof of the fact that the number of minimal dominating sets in a graph on n vertices is at most 1.7159(n), thus improving on the trivial O(2(n)/root n) bound. Our result makes use of the measure-and-conquer technique which was recently developed in the area of exactalgorithms. Based on this result, we derive an O(2.8718(n)) algorithm for the domatic number problem.
暂无评论