Contraction and treewidth lower bounds.
Bodlaender, Hans L., Wolle, Thomas, Koster, Arie M.C.A. (2006)
Journal of Graph Algorithms and Applications
Similarity:
Displaying similar documents to “Theorem proving through depth-first test”
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...
Experiments with the fixed-parameter approach for two-layer planarization.
Suderman, Matthew, Whitesides, Sue (2005)
Journal of Graph Algorithms and Applications
Similarity:
How to find overfull subgraphs in graphs with large maximum degree. II.
Niessen, Thomas (2001)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
A multilevel algorithm for force-directed graph-drawing.
Walshaw, Chris (2003)
Journal of Graph Algorithms and Applications
Similarity:
Satisfiability and matchings in bipartite graphs: relationship and tractability.
Belaid Benhamou (2004)
RACSAM
Similarity:
Satisfiability problem is the task to establish either a given CNF logical formula admits a model or not. It is known to be the canonical NP-complete problem. We study in this note the relationship between matchings in bipartite graphs and the satisfiability problem, and prove that some restrictions of formulae including the known r-r-SAT class are trivially satisfiable. We present an algorithm which finds a model for such formulas in polynomial time complexity if one exists or, failing...
A linear algorithm to recognize maximal generalized outerplanar graphs
José Cáceres, Alberto Márquez (1997)
Mathematica Bohemica
Similarity:
In this work, we get a combinatorial characterization for maximal generalized outerplanar graphs (mgo graphs). This result yields a recursive algorithm testing whether a graph is a mgo graph or not.
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...