Computing branchwidth via efficient triangulations and blocks

2008/09/28 by Fedor V. Fomin, Frédéric Mazoit, Ioan Todinca · 7 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #Mathematics

paper · pdf · doi:10.1016/j.dam.2008.08.009

published in Discrete Applied Mathematics 157(12), 2726-2736 (Elsevier BV)

openalex publication_date 2008/09/28 · crossref created 2008/09/28 · crossref issued 2009/06/01 · crossref published 2009/06/01 · crossref published-print 2009/06/01 · crossref deposited 2025/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/02 · crossref indexed 2026/08/07

Citations

• 3-coloring in time
• Exact Algorithms for NP-Hard Problems: A Survey
• An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Call routing and the ratcatcher
• Graph minors. X. Obstructions to tree-decomposition
• An improved exponential-time algorithm for k -SAT
• Algorithms for maximum independent sets
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• A partial k-arboretum of graphs with bounded treewidth
• Characterizations and algorithmic applications of chordal graph embeddings
• Enumerating maximal independent sets with applications to graph colouring
• A probabilistic algorithm for k-SAT and constraint satisfaction problems

Cited by

• Branch-decomposition [wikipedia]