Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem

DOI10.1007/978-3-540-79723-4_4MaRDI QIDQ3503575zbMATH OpenOpenAlexFDO

Authors Omid Amini, Ignasi Sau, Saket Saurabh

Publication date 5 June 2008

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-79723-4_4

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Parameterized complexity of finding small degree-constrained subgraphs
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
• On the approximability of some degree-constrained subgraph problems
• Finding dense subgraphs of sparse graphs

Cited in

(19)

• The minimum spanning strong subdigraph problem is fixed parameter tractable
• Multiple hypernode hitting sets and smallest two-cores with targets
• The maximum binary tree problem
• An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems
• Parameterized Complexity of Two Edge Contraction Problems with Degree Constraints
• Multi-parameter Complexity Analysis for Constrained Size Graph Problems: Using Greediness for Parameterization
• Tight complexity bounds for FPT subgraph problems parameterized by clique-width
• Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
• On Approximating the d-Girth of a Graph
• Minimum degree up to local complementation: bounds, parameterized complexity, and exact algorithms
• Degree-Constrained Subgraph Problems: Hardness and Approximation Results
• Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems
• Parameterized complexity of connected even/odd subgraph problems
• Parameterized complexity of finding small degree-constrained subgraphs
• Parameterized complexity of three edge contraction problems with degree constraints
• Multiple Hypernode Hitting Sets and Smallest Two-Cores with Targets
• The Maximum Binary Tree Problem.
• Immune sets in monotone infection rules. Characterization and complexity
• Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs

This page was built for publication: Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503575)