Subexponential parameterized algorithms
From MaRDI portal
Publication:458457
DOI10.1016/j.cosrev.2008.02.004zbMath1302.68340OpenAlexW2012313040WikidataQ60488752 ScholiaQ60488752MaRDI QIDQ458457
Dimitrios M. Thilikos, Frederic Dorn, Fedor V. Fomin
Publication date: 7 October 2014
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cosrev.2008.02.004
Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (21)
Linear-Time Computation of a Linear Problem Kernel for Dominating Set on Planar Graphs ⋮ Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Unnamed Item ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Practical algorithms for branch-decompositions of planar graphs ⋮ Subexponential algorithms for partial cover problems ⋮ Catalan structures and dynamic programming in \(H\)-minor-free graphs ⋮ Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions ⋮ Faster parameterized algorithms for minor containment ⋮ Confronting intractability via parameters ⋮ Spanners in sparse graphs ⋮ Implicit branching and parameterized partial cover problems ⋮ Fast minor testing in planar graphs ⋮ Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms ⋮ A Quartic Kernel for Pathwidth-One Vertex Deletion ⋮ Unnamed Item ⋮ Bidimensionality and Kernels ⋮ Planar k-Path in Subexponential Time and Polynomial Space ⋮ Computational study on planar dominating set problem ⋮ Subexponential parameterized algorithms for graphs of polynomial growth
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Linearity of grid minors in treewidth with applications through bidimensionality
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Graph minors. X: Obstructions to tree-decomposition
- Graph minors. XI: Circuits on a surface
- Call routing and the ratcatcher
- Quickly excluding a planar graph
- Graph minors. XVI: Excluding a non-planar graph
- Which problems have strongly exponential complexity?
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- On the existence of subexponential parameterized algorithms
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- Graph minors. XIII: The disjoint paths problem
- Graph minors. XII: Distance on a surface
- Kernels in planar digraphs
- Parametrized complexity theory.
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- New upper bounds on the decomposability of planar graphs
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- The Bidimensional Theory of Bounded-Genus Graphs
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Fourier meets M\"{o}bius: fast subset convolution
- Improved approximation algorithms for minimum-weight vertex separators
- Polynomial-time data reduction for dominating set
- A Cubic Kernel for Feedback Vertex Set
- On Linear Time Minor Tests with Depth-First Search
- Constructive linear time algorithms for branchwidth
- Parameterized complexity: exponential speed-up for planar graph problems
- Mathematical Foundations of Computer Science 2004
- Bidimensional Parameters and Local Treewidth
- Dynamic Programming and Fast Matrix Multiplication
- Automata, Languages and Programming
- Algorithms – ESA 2005
- STACS 2005
- Automata, Languages and Programming
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: Subexponential parameterized algorithms
