Parameterized Complexity of the Smallest Degree-Constrained Subgraph Problem

DOI10.1007/978-3-540-79723-4_4zbMath1142.68450OpenAlexW1512704402MaRDI QIDQ3503575

Ignasi Sau, Omid Amini, 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)

Related Items (10)

Tight Complexity Bounds for FPT Subgraph Problems Parameterized by Clique-Width ⋮ Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems ⋮ Immune sets in monotone infection rules. Characterization and complexity ⋮ The Maximum Binary Tree Problem. ⋮ Degree-Constrained Subgraph Problems: Hardness and Approximation Results ⋮ The maximum binary tree problem ⋮ On Approximating the d-Girth of a Graph ⋮ Multiple hypernode hitting sets and smallest two-cores with targets ⋮ Multiple Hypernode Hitting Sets and Smallest Two-Cores with Targets ⋮ An algorithmic framework for fixed-cardinality optimization in sparse graphs applied to dense subgraph problems

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