A Local Search Algorithm for Branchwidth

DOI10.1007/978-3-642-18381-2_37zbMath1298.05304OpenAlexW1753421735WikidataQ59567574 ScholiaQ59567574MaRDI QIDQ3075536

Arnold Overwijk, Eelko Penninkx, Hans L. Bodlaender

Publication date: 15 February 2011

Published in: SOFSEM 2011: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-18381-2_37

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Finding Good Decompositions for Dynamic Programming on Dense Graphs, A SAT Approach to Branchwidth

Uses Software

• ComputeTW

Cites Work

• Treewidth computations. I: Upper bounds
• Computing branchwidth via efficient triangulations and blocks
• Semi-nice tree-decompositions: the best of branchwidth, treewidth and pathwidth with one algorithm
• Eigenvalues and expanders
• Graph minors. X: Obstructions to tree-decomposition
• A partial k-arboretum of graphs with bounded treewidth
• Call routing and the ratcatcher
• Tour Merging via Branch-Decomposition
• Planar Branch Decompositions I: The Ratcatcher
• Planar Branch Decompositions II: The Cycle Method
• New upper bounds on the decomposability of planar graphs
• Treewidth: Characterizations, Applications, and Computations
• Graph minors. II. Algorithmic aspects of tree-width
• Constructive linear time algorithms for branchwidth
• A Branch and Bound Algorithm for Exact, Upper, and Lower Bounds on Treewidth
• Algorithms – ESA 2005
• Heuristic and metaheuristic methods for computing graph treewidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Automata, Languages and Programming
• Unnamed Item