Parameterized complexity of finding small degree-constrained subgraphs
type: Item
instance of: scholarly article
title: Parameterized complexity of finding small degree-constrained subgraphs
zbMATH Open document ID: 1242.68119
author: Omid Amini
author: Ignasi Sau
author: Saket Saurabh
published in: Journal of Discrete Algorithms
publication date: 2012-05-11T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 6033167
zbMATH Keywords: parameterized complexity
zbMATH Keywords: degree-constrained subgraph
zbMATH Keywords: fixed-parameter tractable algorithm
zbMATH Keywords: \(W[1]\)-hardness
zbMATH Keywords: treewidth
zbMATH Keywords: dynamic programming
zbMATH Keywords: excluded minors
MaRDI profile type: Publication
full work available at URL: j.jda.2011.05.001
OpenAlex ID: W2069471278
cites work: Degree-Constrained Subgraph Problems: Hardness and Approximation Results
cites work: Hardness and approximation of traffic grooming
cites work: Finding Dense Subgraphs with Size Bounds
cites work: Induced Subgraphs of the Power of a Cycle
cites work: Long cycles in graphs with no subgraphs of minimal degree 3
cites work: The complexity of uniform Nash equilibria and related regular subgraph problems
cites work: Maximum \(k\)-regular induced subgraphs
cites work: The complexity of regular subgraph recognition
cites work: Connected Coloring Completion for General Graphs: Algorithms and Complexity
cites work: The ring grooming problem
cites work: Three‐regular subgraphs of four‐regular graphs
cites work: Q5501346
cites work: Q4393480
cites work: Diameter and treewidth in minor-closed graph families
cites work: Q3804734
cites work: Subgraphs of minimal degree \(k\)
cites work: The dense \(k\)-subgraph problem
cites work: On the parameterized complexity of multiple-interval graph problems
cites work: Parametrized complexity theory.
cites work: Deciding first-order properties of locally tree-decomposable structures
cites work: Q4198056
cites work: Local tree-width, excluded minors, and approximation algorithms
cites work: Approximation algorithms for finding low-degree subgraphs
cites work: Parameterized complexity of finding regular induced subgraphs
cites work: Q5710169
cites work: A note on the complexity of finding regular subgraphs
cites work: Graph minors. XVI: Excluding a non-planar graph
cites work: Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
cites work: Finding regular subgraphs in both arbitrary and planar graphs
DOI: 10.1016/J.JDA.2011.05.001
description: scientific article; zbMATH DE number 6033167