On the existence of subexponential parameterized algorithms
From MaRDI portal
Recommendations
- Subexponential Parameterized Algorithms
- Subexponential parameterized algorithms
- Parameterized complexity and subexponential-time computability
- Parameterized (in)approximability of subset problems
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- An Isomorphism Between Subexponential and Parameterized Complexity Theory
- Exploring subexponential parameterized complexity of completion problems
- scientific article; zbMATH DE number 1754598
- Subexponential parameterized algorithms for graphs of polynomial growth
Cites work
- scientific article; zbMATH DE number 1617251 (Why is no real title available?)
- scientific article; zbMATH DE number 1304341 (Why is no real title available?)
- scientific article; zbMATH DE number 1341905 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 1754598 (Why is no real title available?)
- scientific article; zbMATH DE number 1756013 (Why is no real title available?)
- scientific article; zbMATH DE number 806748 (Why is no real title available?)
- A general method to speed up fixed-parameter-tractable algorithms
- An improved fixed-parameter algorithm for vertex cover
- Circuit Bottom Fan-in and Computational Power
- Faster exact algorithms for hard problems: A parameterized point of view
- Fixed-parameter tractability and completeness. IV: On completeness for W\([\) P\(]\) and PSPACE analogues
- Introduction to algorithms
- Nondeterminism within $P^ * $
- On fixed-parameter tractability and approximability of NP optimization problems
- On the structure of parameterized problems in NP
- Optimization, approximation, and complexity classes
- Some simplified NP-complete graph problems
- The Complexity of Decision Versus Search
- Vertex cover: Further observations and further improvements
- Vertex packings: Structural properties and algorithms
- Which problems have strongly exponential complexity?
Cited in
(48)- A novel parameterised approximation algorithm for \textsc{minimum vertex cover}
- Dynamic programming for graphs on surfaces
- Coverability and sub-exponential parameterized algorithms in planar graphs
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- Kernelization: new upper and lower bound techniques
- Exponential time paradigms through the polynomial time lens
- Tight lower bounds for certain parameterized NP-hard problems
- A technique for obtaining true approximations for \(k\)-center with covering constraints
- A basic parameterized complexity primer
- Graph minors and parameterized algorithm design
- Improved upper bounds for vertex cover
- (Total) vector domination for graphs with bounded branchwidth
- Subexponential fixed-parameter algorithms for partial vector domination
- Approximability of clique transversal in perfect graphs
- Slightly superexponential parameterized problems
- On the parameterized vertex cover problem for graphs with perfect matching
- Parameterized Algorithms for Generalized Domination
- Tight complexity bounds for FPT subgraph problems parameterized by clique-width
- On Parameterized Exponential Time Complexity
- On the computational hardness based on linear fpt-reductions
- Fixed-parameter approximation: conceptual framework and approximability results
- Large independent sets in subquartic planar graphs
- scientific article; zbMATH DE number 1754598 (Why is no real title available?)
- Subexponential parameterized algorithms
- Confronting intractability via parameters
- Analysis parameterized algorithms on the bases of elasticity to functions complexity
- Hitting forbidden subgraphs in graphs of bounded treewidth
- Parameterized and subexponential-time complexity of satisfiability problems and applications
- On parameterized exponential time complexity
- Parameterized computation and complexity: a new approach dealing with NP-hardness
- Parameterized algorithms for feedback set problems and their duals in tournaments
- A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
- Kernels in planar digraphs
- Faster parameterized algorithms for deletion to split graphs
- The constant inapproximability of the parameterized dominating set problem
- Parameterized approximation via fidelity preserving transformations
- Parameterized complexity and subexponential-time computability
- An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
- Fixed-parameter tractable algorithm and polynomial kernel for \textsc{Max-Cut Above Spanning Tree}
- scientific article; zbMATH DE number 3936499 (Why is no real title available?)
- Exact algorithms for the Hamiltonian cycle problem in planar graphs
- Component order connectivity in directed graphs
- Component order connectivity in directed graphs
- Structure of polynomial-time approximation
- Solving vertex cover in polynomial time on hyperbolic random graphs
- Vertex cover, dominating set and my encounters with parameterized complexity and Mike Fellows
- \textsc{Max-Cut} parameterized above the Edwards-Erdős bound
- Genus characterizes the complexity of certain graph problems: Some tight results
This page was built for publication: On the existence of subexponential parameterized algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1877709)
