A \(c^k n\) 5-approximation algorithm for treewidth
type: Item
instance of: scholarly article
zbMATH Open document ID: 1333.05282
DOI: 10.1137/130947374
author: Pål Grønås Drange
author: Markus S. Dregi
author: Fedor V. Fomin
author: Daniel Lokshtanov
author: Michał Pilipczuk
author: Hans L. Bodlaender
published in: SIAM Journal on Computing
publication date: 2016-04-11T00:00:00Z
full work available at URL: https://arxiv.org/abs/1304.6321
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 6566956
zbMATH Keywords: algorithms
zbMATH Keywords: graphs
zbMATH Keywords: treewidth
zbMATH Keywords: approximation
zbMATH Keywords: fixed parameter tractability
Wikidata QID: Q59567401
MaRDI profile type: Publication
OpenAlex ID: W2313886575
arXiv ID: 1304.6321
cites work: Q4273870
cites work: Approximation algorithms for treewidth
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems
cites work: Q3795218
cites work: A linear time algorithm for finding tree-decompositions of small treewidth
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Deterministic Single Exponential Time Algorithms for Connectivity Problems Parameterized by Treewidth
cites work: Equitable colorings of bounded treewidth graphs
cites work: Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
cites work: Parallel Algorithms with Optimal Speedup for Bounded Treewidth
cites work: Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
cites work: Shortest paths in digraphs of small treewidth. II: Optimal parallel algorithms
cites work: Shortest paths in digraphs of small treewidth. I: Sequential algorithms
cites work: Q4234136
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Fast Hamiltonicity Checking Via Bases of Perfect Matchings
cites work: Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
cites work: Improved Approximation Algorithms for Minimum Weight Vertex Separators
cites work: Q3328583
cites work: Dynamic algorithms for graphs of bounded treewidth
cites work: Treewidth. Computations and approximations
cites work: Solving partial constraint satisfaction problems with tree decomposition
cites work: Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
cites work: Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
cites work: Parameterized graph separation problems
cites work: Parallel Tree Contraction Part 2: Further Applications
cites work: AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Q4344138
cites work: Algorithms for Vertex Partitioning Problems on Partial k-Trees
DBLP publication ID: journals/siamcomp/BodlaenderDDFLP16
title: A \(c^k n\) 5-approximation algorithm for treewidth
description: scientific article; zbMATH DE number 6566956