Editing graphs to satisfy degree constraints: a parameterized approach
type: Item
instance of: scholarly article
title: Editing graphs to satisfy degree constraints: a parameterized approach
zbMATH Open document ID: 1242.68124
author: Luke Mathieson
author: Stefan Szeider
published in: Journal of Computer and System Sciences
publication date: 2012-05-11T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6033487
zbMATH Keywords: parameterized complexity
zbMATH Keywords: computational complexity
zbMATH Keywords: kernelization
zbMATH Keywords: graph editing
zbMATH Keywords: regular subgraph
zbMATH Keywords: general factor
MaRDI profile type: Publication
full work available at URL: j.jcss.2011.02.001
OpenAlex ID: W2081215656
cites work: Kernels: Annotated, Proper and Induced
cites work: An algorithmic proof of Tutte's f-factor theorem
cites work: Finding a \(\Delta\)-regular supergraph of minimum order
cites work: Induced matchings
cites work: Maximum \(k\)-regular induced subgraphs
cites work: The complexity of regular subgraph recognition
cites work: Tight lower bounds for certain parameterized NP-hard problems
cites work: Three‐regular subgraphs of four‐regular graphs
cites work: General factors of graphs
cites work: Q4263467
cites work: Q4393480
cites work: Paths, Trees, and Flowers
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: Combinatorial optimization. Theory and algorithms.
cites work: The factorization of graphs. II
cites work: Antifactors of graphs
cites work: Matching theory
cites work: Parameterized Graph Editing with Chosen Vertex Degrees
cites work: Parameterized complexity of finding regular induced subgraphs
cites work: Q5710169
cites work: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
cites work: A note on the complexity of finding regular subgraphs
cites work: General antifactors of graphs
cites work: Deciding whether a planar graph has a cubic subgraph is NP-complete
cites work: Finding regular subgraphs in both arbitrary and planar graphs
cites work: On locating cubic subgraphs in bounded-degree connected bipartite graphs
cites work: On the fixed-parameter tractability of parameterized model-checking problems
cites work: NP-completeness of some generalizations of the maximum matching problem
cites work: A Short Proof of the Factor Theorem for Finite Graphs
cites work: Spanning subgraphs with specified valencies
cites work: Graph factors
DOI: 10.1016/J.JCSS.2011.02.001
description: scientific article; zbMATH DE number 6033487