Computing branchwidth via efficient triangulations and blocks

DOI10.1016/J.DAM.2008.08.009zbMath1211.05163DBLPjournals/dam/FominMT09OpenAlexW2052451108WikidataQ60488671 ScholiaQ60488671MaRDI QIDQ967315

Fedor V. Fomin, Ioan Todinca, Frédéric Mazoit

Publication date: 28 April 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.08.009

zbMATH Keywords

graphbranchwidthexponential time algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Tangle bases: Revisited ⋮ A combinatorial optimization algorithm for solving the branchwidth problem ⋮ A Local Search Algorithm for Branchwidth ⋮ A SAT Approach to Branchwidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Satisfiability, branch-width and Tseitin tautologies
• Enumerating maximal independent sets with applications to graph colouring.
• Graph minors. X: Obstructions to tree-decomposition
• A partial k-arboretum of graphs with bounded treewidth
• Call routing and the ratcatcher
• Characterizations and algorithmic applications of chordal graph embeddings
• Computing the branchwidth of interval graphs
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Tour Merging via Branch-Decomposition
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• New upper bounds on the decomposability of planar graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• The Branch-Width of Circular-Arc Graphs
• Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
• An improved exponential-time algorithm for k -SAT
• Measure and conquer
• An O(2^0.304n) Algorithm for Solving Maximum Independent Set Problem
• Algorithms for maximum independent sets
• 3-coloring in time
• Treewidth and Pathwidth of Permutation Graphs
• Automata, Languages and Programming
• Algorithms – ESA 2005
• Algorithms – ESA 2005
• Automata, Languages and Programming

This page was built for publication: Computing branchwidth via efficient triangulations and blocks