Displaying similar documents to “Experiments with the fixed-parameter approach for two-layer planarization.”

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 Capacitated Arc Routing Problem. A heuristic algorithm.

Enrique. Benavent, V. Campos, Angel Corberán, Enrique Mota (1990)

Qüestiió

Similarity:

In this paper we consider the Capacitated Arc Routing Problem, in which a fleet of K vehicles, all of them based on a specific vertex (the depot) and with a known capacity Q, must service a subset of the edges of the graph, with minimum total cost and such that the load assigned to each vehicle does not exceed its capacity. A heuristic algorithm for this problem is proposed consisting of: the selection of K centers, the construction of K connected graphs with associated loads...