Computing branchwidth via efficient triangulations and blocks
type: Item
instance of: scholarly article
title: Computing branchwidth via efficient triangulations and blocks
zbMATH Open document ID: 1211.05163
author: Fedor V. Fomin
author: Frédéric Mazoit
author: Ioan Todinca
published in: Discrete Applied Mathematics
publication date: 2010-04-28T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5702588
zbMATH Keywords: graph
zbMATH Keywords: branchwidth
zbMATH Keywords: exponential time algorithm
MaRDI profile type: Publication
full work available at URL: j.dam.2008.08.009
OpenAlex ID: W2052451108
Wikidata QID: Q60488671
cites work: Satisfiability, branch-width and Tseitin tautologies
cites work: 3-coloring in time
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Treewidth and Pathwidth of Permutation Graphs
cites work: Treewidth and minimum fill-in: Grouping the minimal separators
cites work: Enumerating maximal independent sets with applications to graph colouring.
cites work: Tour merging via branch-decomposition
cites work: Q3619797
cites work: A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
cites work: Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
cites work: Algorithms – ESA 2005
cites work: Measure and conquer
cites work: Automata, Languages and Programming
cites work: Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
cites work: New upper bounds on the decomposability of planar graphs
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Q3328583
cites work: Q5501274
cites work: An O(20.304n) Algorithm for Solving Maximum Independent Set Problem
cites work: Computing the branchwidth of interval graphs
cites work: The Branch-Width of Circular-Arc Graphs
cites work: Characterizations and algorithmic applications of chordal graph embeddings
cites work: An improved exponential-time algorithm for k -SAT
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Algorithms for maximum independent sets
cites work: Call routing and the ratcatcher
cites work: Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In
cites work: A new algorithm for optimal 2-constraint satisfaction and its implications
cites work: Q4414647
DBLP publication ID: journals/dam/FominMT09
DOI: 10.1016/J.DAM.2008.08.009
description: scientific article; zbMATH DE number 5702588