Heuristic and metaheuristic methods for computing graph treewidth

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

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

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 experiments; treewidth; heuristic; triangulated graphs; metaheuristic; elimination orderings

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

90C59: Approximation methods and heuristics in mathematical programming

Related Items

Achievable sets, brambles, and sparse treewidth obstructions, Treewidth lower bounds with brambles, Treewidth computations. I: Upper bounds, On the maximum cardinality search lower bound for treewidth, Tree decomposition and discrete optimization problems: a survey, Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization, A Local Search Algorithm for Branchwidth

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