scientific article; zbMATH DE number 7205188

DOI10.4230/LIPIcs.IPEC.2017.4zbMath1443.68120MaRDI QIDQ5111863

Ignasi Sau, Julien Baste, Dimitrios M. Thilikos

Publication date: 27 May 2020

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

zbMATH Keywords

dynamic programmingtreewidthparameterized complexitygraph minorsexponential time hypothesistopological minorshitting minors

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (7)

Compactors for parameterized counting problems ⋮ A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms ⋮ Hitting minors on bounded treewidth graphs. III. Lower bounds ⋮ Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms ⋮ Modification to Planarity is Fixed Parameter Tractable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The node-deletion problem for hereditary properties is NP-complete
• Graph minors. X: Obstructions to tree-decomposition
• Which problems have strongly exponential complexity?
• 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
• A tight lower bound for vertex planarization on graphs of bounded treewidth
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems
• (Meta) Kernelization
• Explicit Linear Kernels via Dynamic Programming
• Deleting vertices to bound path length
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• A Near-Optimal Planarization Algorithm
• Bidimensionality and Geometric Graphs
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• On the number of labeled graphs of bounded treewidth

This page was built for publication: