Subexponential parameterized algorithms
From MaRDI portal
Publication:458457
DOI10.1016/J.COSREV.2008.02.004zbMATH Open1302.68340DBLPjournals/csr/DornFT08OpenAlexW2012313040WikidataQ60488752 ScholiaQ60488752MaRDI QIDQ458457FDOQ458457
Authors: Frederic Dorn, Fedor V. Fomin, Dimitrios M. Thilikos 
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
Recommendations
- Subexponential Parameterized Algorithms
- On the existence of subexponential parameterized algorithms
- Sublinear-time Algorithms
- Sublinear time algorithms
- scientific article; zbMATH DE number 5057523
- Parameterized complexity and subexponential-time computability
- Parameterized (in)approximability of subset problems
- Subexponential parameterized algorithms for graphs of polynomial growth
- Subexponential parameterized algorithm for interval completion
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)
Cites Work
- Title not available (Why is that?)
- Graph minors. X: Obstructions to tree-decomposition
- Call routing and the ratcatcher
- Which problems have strongly exponential complexity?
- Graph minors. XIII: The disjoint paths problem
- Parametrized complexity theory.
- Graphs on surfaces
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Linear time algorithms for NP-hard problems restricted to partial k- trees
- Quickly excluding a planar graph
- Title not available (Why is that?)
- Title not available (Why is that?)
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- On Linear Time Minor Tests with Depth-First Search
- On the existence of subexponential parameterized algorithms
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- Constructive linear time algorithms for branchwidth
- Dynamic Programming and Fast Matrix Multiplication
- Graph-Theoretic Concepts in Computer Science
- Polynomial-time data reduction for dominating set
- Bidimensionality: new connections between FPT algorithms and PTASs
- Fourier meets M\"{o}bius: fast subset convolution
- New upper bounds on the decomposability of planar graphs
- Mathematical Foundations of Computer Science 2004
- Graph minors. XVI: Excluding a non-planar graph
- Linearity of grid minors in treewidth with applications through bidimensionality
- Graph minors. XII: Distance on a surface
- Bidimensional Parameters and Local Treewidth
- Graph minors. XI: Circuits on a surface
- Kernels in planar digraphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Parameterized complexity: exponential speed-up for planar graph problems
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- Title not available (Why is that?)
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
- Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
- Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
- The Bidimensional Theory of Bounded-Genus Graphs
- Improved approximation algorithms for minimum-weight vertex separators
- A Cubic Kernel for Feedback Vertex Set
- Title not available (Why is that?)
- Automata, Languages and Programming
- Algorithms – ESA 2005
- STACS 2005
- Automata, Languages and Programming
- The complexity of graph contractions.
Cited In (36)
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Title not available (Why is that?)
- Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
- Spanners in sparse graphs
- Graph minors and parameterized algorithm design
- Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
- Subexponential-time parameterized algorithm for Steiner tree on planar graphs
- Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
- Fast minor testing in planar graphs
- A quartic kernel for pathwidth-one vertex deletion
- Implicit branching and parameterized partial cover problems
- Title not available (Why is that?)
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Subexponential parameterized algorithms for graphs of polynomial growth
- Subexponential Parameterized Algorithms
- Optimizations of the subresultant algorithm
- New analysis and computational study for the planar connected dominating set problem
- Sublinear Computation Paradigm
- Catalan structures and dynamic programming in \(H\)-minor-free graphs
- Confronting intractability via parameters
- Practical algorithms for branch-decompositions of planar graphs
- Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
- On the existence of subexponential parameterized algorithms
- Planar \(k\)-path in subexponential time and polynomial space
- Subexponential algorithms for partial cover problems
- Faster parameterized algorithms for minor containment
- Subexponential parameterized algorithms for bounded-degree connected subgraph problems on planar graphs
- Computational study on planar dominating set problem
- Title not available (Why is that?)
- Fast sub-exponential algorithms and compactness in planar graphs
- Towards a Taxonomy of Techniques for Designing Parameterized Algorithms
- Bidimensionality and kernels
- Title not available (Why is that?)
- Linear-time computation of a linear problem kernel for dominating set on planar graphs
- Title not available (Why is that?)
This page was built for publication: Subexponential parameterized algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458457)
