Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width
From MaRDI portal
Publication:2891349
DOI10.1007/978-3-642-28050-4_17zbMath1352.68095OpenAlexW1882421805MaRDI QIDQ2891349
Viresh Patel, Petr A. Golovach, Hajo J. Broersma
Publication date: 15 June 2012
Published in: Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-28050-4_17
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Strong computational lower bounds via parameterized complexity
- The complexity of regular subgraph recognition
- Parameterized complexity of finding regular induced subgraphs
- Clustering and domination in perfect graphs
- Deciding whether a planar graph has a cubic subgraph is NP-complete
- \(k\)-NLC graphs and polynomial algorithms
- On locating cubic subgraphs in bounded-degree connected bipartite graphs
- Which problems have strongly exponential complexity?
- On the existence of subexponential parameterized algorithms
- Finding regular subgraphs in both arbitrary and planar graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Approximating clique-width and branch-width
- On the computational hardness based on linear fpt-reductions
- Tight lower bounds for certain parameterized NP-hard problems
- Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem
- Capacitated Domination and Covering: A Parameterized Perspective
- Clique-Width is NP-Complete
- Degree-Constrained Subgraph Problems: Hardness and Approximation Results
- Planar Capacitated Dominating Set Is W[1-Hard]
- Greedily Finding a Dense Subgraph
- Finding Branch-Decompositions and Rank-Decompositions
- Three‐regular subgraphs of four‐regular graphs
- The dense \(k\)-subgraph problem
This page was built for publication: Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width
