Heuristic and metaheuristic methods for computing graph treewidth

DOI10.1051/RO:2004011MaRDI QIDQ5479837zbMATH OpenOpenAlexFDO

Authors François Clautiaux, A. Moukrim, Stéphane Nègre, Jacques Carlier

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, https://eudml.org/doc/105299, https://semanticscholar.org/paper/90fd6d6198178ebc453edec611d8178a4649e856

zbMATH Keywords

computational experimentselimination orderingsheuristicmetaheuristictreewidthtriangulated graphs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1982177
• On Exact Algorithms for Treewidth
• Treewidth computations. I: Upper bounds
• An Iterative Heuristic Algorithm for Tree Decomposition
• Experimental and Efficient Algorithms

Cites work

• A decomposition algorithm for network reliability evaluation
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A survey of very large-scale neighborhood search techniques
• 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
• Characterization and Recognition of Partial 3-Trees
• Complexity of Finding Embeddings in a k-Tree
• Evaluating network reliability and 2-edge-connected reliability in linear time for bounded pathwidth graphs
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 4178809 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 1016966 (Why is no real title available?)
• scientific article; zbMATH DE number 1062113 (Why is no real title available?)
• scientific article; zbMATH DE number 1982177 (Why is no real title available?)
• scientific article; zbMATH DE number 3420184 (Why is no real title available?)
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Treewidth: computational experiments
• Triangulated graphs and the elimination process

Cited in

(19)

• Turbocharging treewidth heuristics
• Tractability of most probable explanations in multidimensional Bayesian network classifiers
• New metaheuristic approaches for the edge-weighted k-cardinality tree problem
• Learning tractable Bayesian networks in the space of elimination orders
• Tree decomposition and discrete optimization problems: a survey
• Preprocessing for Treewidth: A Combinatorial Analysis through Kernelization
• A local search algorithm for branchwidth
• AND/OR graph heuristic search methods
• scientific article; zbMATH DE number 1982177 (Why is no real title available?)
• scientific article; zbMATH DE number 2013546 (Why is no real title available?)
• Turbocharging treewidth heuristics
• scientific article; zbMATH DE number 7310078 (Why is no real title available?)
• Computational aspects of treewidth for graph
• Experimental and Efficient Algorithms
• A note on exact algorithms for vertex ordering problems on graphs
• 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

Describes a project that uses

Uses Software

• DIMACS
• Tabu search

This page was built for publication: Heuristic and metaheuristic methods for computing graph treewidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5479837)