Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Heuristic and metaheuristic methods for computing graph treewidth

François ClautiauxAziz MoukrimStéphane NègreJacques Carlier — 2004

RAIRO - Operations Research - Recherche Opérationnelle

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 large. The...

Heuristic and metaheuristic methods for computing graph treewidth

François ClautiauxAziz MoukrimStéphane NègreJacques Carlier — 2010

RAIRO - Operations Research

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 large....

Page 1

Download Results (CSV)