Exact exponential algorithms Page 1 80 coMMunicATions of ThE AcM | MARCh 2013 | Vol. 56
| No. 3 review articles Exact Exponential Algorithms of non-parameterized instances of intractable …

For more than 40 years, Branch & Reduce exponential-time backtracking algorithms have
been among the most common tools used for finding exact solutions of NP-hard problems …

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 …

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 …

The topic of exact, exponential-time algorithms for NP-hard problems has received a lot of
attention, particularly with the focus of producing algorithms with stronger theoretical …

We present a time O(1.7548^n) algorithm finding a minimum feedback vertex set in an
undirected graph on n vertices. We also prove that a graph on n vertices can contain at most …

Branch & Reduce and dynamic programming on graphs of bounded treewidth are among
the most common and powerful techniques used in the design of moderately exponential …

We show that the treewidth and the minimum fill-in of an n-vertex graph can be computed in
time O(1.8899^n). Our results are based on combinatorial proofs that an n-vertex graph has …

For a given graph G and integers b, f≥ 0, let S be a subset of vertices of G of size b+ 1 such
that the subgraph of G induced by S is connected and S can be separated from other …

In the connected dominating set problem we are given an n-node undirected graph, and we
are asked to find a minimum cardinality connected subset S of nodes such that each node …