Computing branchwidth via efficient triangulations and blocks
From MaRDI portal
Publication:967315
DOI10.1016/j.dam.2008.08.009zbMath1211.05163OpenAlexW2052451108WikidataQ60488671 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
Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
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(20.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
