Parameterized complexity of finding small degree-constrained subgraphs
From MaRDI portal
Publication:414424
DOI10.1016/j.jda.2011.05.001zbMath1242.68119OpenAlexW2069471278MaRDI QIDQ414424
Omid Amini, Ignasi Sau, Saket Saurabh
Publication date: 11 May 2012
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2011.05.001
dynamic programmingtreewidthexcluded minorsparameterized complexity\(W[1\)-hardness]degree-constrained subgraphfixed-parameter tractable algorithm
Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Increasing the Minimum Degree of a Graph by Contractions ⋮ Complexity and Kernels for Bipartition into Degree-bounded Induced Graphs ⋮ Increasing the minimum degree of a graph by contractions ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ Minimum k‐cores and the k‐core polytope ⋮ On the approximability of some degree-constrained subgraph problems ⋮ On approximating the \(d\)-girth of a graph ⋮ Complexity and kernels for bipartition into degree-bounded induced graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Subgraphs of minimal degree \(k\)
- Hardness and approximation of traffic grooming
- The complexity of regular subgraph recognition
- The complexity of uniform Nash equilibria and related regular subgraph problems
- Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
- On the parameterized complexity of multiple-interval graph problems
- Parameterized complexity of finding regular induced subgraphs
- A note on the complexity of finding regular subgraphs
- Long cycles in graphs with no subgraphs of minimal degree 3
- Graph minors. XVI: Excluding a non-planar graph
- Diameter and treewidth in minor-closed graph families
- Finding regular subgraphs in both arbitrary and planar graphs
- Maximum \(k\)-regular induced subgraphs
- Parametrized complexity theory.
- Local tree-width, excluded minors, and approximation algorithms
- Deciding first-order properties of locally tree-decomposable structures
- Induced Subgraphs of the Power of a Cycle
- Finding Dense Subgraphs with Size Bounds
- Degree-Constrained Subgraph Problems: Hardness and Approximation Results
- Connected Coloring Completion for General Graphs: Algorithms and Complexity
- The ring grooming problem
- Approximation algorithms for finding low-degree subgraphs
- Three‐regular subgraphs of four‐regular graphs
- The dense \(k\)-subgraph problem
