Contraction and treewidth lower bounds.

Bodlaender, Hans L.; Wolle, Thomas; Koster, Arie M.C.A.

Displaying similar documents to “Contraction and treewidth lower bounds.”

Heuristic and metaheuristic methods for computing graph treewidth

François Clautiaux, Aziz Moukrim, Stéphane Nègre, Jacques Carlier (2004)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

The notion of treewidth is of considerable interest in relation to NP-hard problems. Indeed, several studies have shown that the tree-decomposition method can be used to solve many basic optimization problems in polynomial time when treewidth is bounded, even if, for arbitrary graphs, computing the treewidth is NP-hard. Several papers present heuristics with computational experiments. For many graphs the discrepancy between the heuristic results and the best lower bounds is still very...

The bondage number of graphs: good and bad vertices

Vladimir Samodivkin (2008)

Discussiones Mathematicae Graph Theory

Similarity:

The domination number γ(G) of a graph G is the minimum number of vertices in a set D such that every vertex of the graph is either in D or is adjacent to a member of D. Any dominating set D of a graph G with |D| = γ(G) is called a γ-set of G. A vertex x of a graph G is called: (i) γ-good if x belongs to some γ-set and (ii) γ-bad if x belongs to no γ-set. The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph...