Turbocharging treewidth heuristics

DOI10.1007/s00453-018-0499-1zbMath1411.68144OpenAlexW2886839616WikidataQ129369153 ScholiaQ129369153MaRDI QIDQ1725636

Julián Mestre, Joachim Gudmundsson, Stefan Rümmele, Serge Gaspers, Mitchell Jones

Publication date: 14 February 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/6932/

zbMATH Keywords

local searchtree decompositionheuristicfixed-parameter tractability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Finding Hamiltonian Cycle in Graphs of Bounded Treewidth

Uses Software

• ComputeTW
• GitHub
• tw-heuristic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Incremental list coloring of graphs, parameterized by conservation
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Treewidth computations. I: Upper bounds
• Complexity of Finding Embeddings in a k-Tree
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth