scientific article; zbMATH DE number 7205191

DOI10.4230/LIPIcs.IPEC.2017.7zbMath1443.68121MaRDI QIDQ5111866

Édouard Bonnet, O-joung Kwon, Dániel Marx, Nick Brettell

Publication date: 27 May 2020

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

treewidthfeedback vertex setfixed-parameter tractable algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (4)

Parameterized Complexity of Safe Set ⋮ Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms ⋮ Optimality program in segment and string graphs ⋮ Hitting minors on bounded treewidth graphs. III. Lower bounds

Cites Work

• On the computational complexity of vertex integrity and component order connectivity
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property
• Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• An Exact Algorithm for Minimum Distortion Embedding
• On the number of labeled graphs of bounded treewidth
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: