The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like DOMINATING SET and INDEPENDENT SET. This approach is used in this paper to obtain a faster ...
详细信息
The measure and conquer approach has proven to be a powerful tool to analyse exact algorithms for combinatorial problems like DOMINATING SET and INDEPENDENT SET. This approach is used in this paper to obtain a faster exact algorithm for DOMINATING SET. We obtain this algorithm by considering a series of branch and reduce algorithms. This series is the result of an iterative process in which a mathematical analysis of an algorithm in the series with measure and conquer results in a convex or quasiconvex programming problem. The solution, by means of a computer, to this problem not only gives a bound on the running time of the algorithm, but can also give an indication on where to look for a new reduction rule, often giving a new, possibly faster algorithm. As a result, we obtain an O(1.4969(n)) time and polynomial space algorithm. (C) 2011 Elsevier B.V. All rights reserved.
We show that the 3-colorability problem can be solved in O(1.296(n)) time on any n-vertex graph with minimum degree at least 15. This algorithm is obtained by constructing a dominating set of the graph greedily, enume...
详细信息
We show that the 3-colorability problem can be solved in O(1.296(n)) time on any n-vertex graph with minimum degree at least 15. This algorithm is obtained by constructing a dominating set of the graph greedily, enumerating all possible 3-colorings of the dominating set, and then solving the resulting 2-list coloring instances in polynomial time. We also show that a 3-coloring can be obtained in 2(o(n)) time for graphs having minimum degree at least w(n) where w(n) is any function which goes to infinity. We also show that if the lower bound on minimum degree is replaced by a constant (however large it may be), then neither a 2(o(n)) time nor a 2(o(m)) time algorithm is possible (m denotes the number of edges) for 3-colorability unless exponentialtime Hypothesis (ETH) fails. We also describe an algorithm which obtains a 4-coloring of a 3-colorable graph in O(1.2535(n)) time. (C) 2010 Elsevier B.V. All rights reserved.
Iterative compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard ...
详细信息
Iterative compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard problems. We exemplify our findings with algorithms for the MAXIMUM INDEPENDENT SET problem, a parameterized and a counting version of d-HITTING SET and the MAXIMUM INDUCED CLUSTER SUBGRAPH problem. (C) 2009 Elsevier B.V. All rights reserved.
In this paper we present a faster exact exponentialtime algorithm for the edge dominating set problem. Our algorithm uses O(1.3226(n)) time and polynomial space. The algorithm combines an enumeration approach based o...
详细信息
ISBN:
(纸本)9783540797227
In this paper we present a faster exact exponentialtime algorithm for the edge dominating set problem. Our algorithm uses O(1.3226(n)) time and polynomial space. The algorithm combines an enumeration approach based on enumerating minimal vertex covers with the branch and reduce paradigm. Its time bound is obtained using the measure and conquer technique. The algorithm is obtained by starting with a slower algorithm which is refined stepwise. In this way a series of algorithms appears, each one slightly faster than the previous, resulting in the O(1.3226(n)) time algorithm. The techniques also gives faster exact algorithms for: minimum weight edge dominating set, minimum (weight) maximal matching, matrix domination and the parametrised version of minimum weight maximal matching.
A subset of vertices D subset of V of a graph G = (V, E) is a dominating clique if D is a dominating set and a clique of G. The existence problem 'Given a graph G, is there a dominating clique in G?' is NP-com...
详细信息
A subset of vertices D subset of V of a graph G = (V, E) is a dominating clique if D is a dominating set and a clique of G. The existence problem 'Given a graph G, is there a dominating clique in G?' is NP-complete, and thus both the Minimum and the Maximum Dominating Clique problems are NP-hard. We present an O(1.3387(n)) time and polynomial space algorithm that for an input graph on n vertices either computes a minimum dominating clique or reports that the graph has no dominating clique. The algorithm uses the Branch & Reduce paradigm and its time analysis is based on the Measure & Conquer approach. We also establish a lower bound of Omega(1.2599(n)) for the worst case running time of the algorithm. Finally using memorization we obtain an O(1.3234(n)) time and exponential space algorithm for the same problem. (c) 2007 Elsevier B.V. All rights reserved.
暂无评论