Displaying similar documents to “Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring.”

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

Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP

Edith Hemaspaandra, Jörg Rothe, Holger Spakowski (2006)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

For both the edge deletion heuristic and the maximum-degree greedy heuristic, we study the problem of recognizing those graphs for which that heuristic can approximate the size of a minimum vertex cover within a constant factor of r , where r is a fixed rational number. Our main results are that these problems are complete for the class of problems solvable via parallel access to NP . To achieve these main results, we also show that the restriction of the vertex cover problem to those graphs...