Heuristic and metaheuristic methods for computing graph treewidth

DOI10.1051/ro:2004011zbMath1092.90065OpenAlexW2125547222MaRDI QIDQ5479837

Jacques Carlier, François Clautiaux, Stéphane Negre, Aziz Moukrim

Publication date: 11 July 2006

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=RO_2004__38_1_13_0

zbMATH Keywords

computational experimentstreewidthheuristictriangulated graphsmetaheuristicelimination orderings

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59)

Related Items

Achievable sets, brambles, and sparse treewidth obstructions, Treewidth lower bounds with brambles, Tractability of most probable explanations in multidimensional Bayesian network classifiers, Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization, Tree decomposition and discrete optimization problems: a survey, A note on exact algorithms for vertex ordering problems on graphs, Treewidth computations. I: Upper bounds, On the maximum cardinality search lower bound for treewidth, A Local Search Algorithm for Branchwidth, Learning tractable Bayesian networks in the space of elimination orders, Unnamed Item, Unnamed Item

Uses Software

• DIMACS
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A survey of very large-scale neighborhood search techniques
• Evaluating network reliability and 2-edge-connected reliability in linear time for bounded pathwidth graphs
• A decomposition algorithm for network reliability evaluation
• Triangulated graphs and the elimination process
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Characterization and Recognition of Partial 3-Trees
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Algorithmic Aspects of Vertex Elimination on Graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth