Heuristic and metaheuristic methods for computing graph treewidth
François Clautiaux, Aziz Moukrim, Stéphane Nègre, Jacques Carlier (2010)
RAIRO - Operations Research
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...