Editing graphs to satisfy degree constraints: a parameterized approach
From MaRDI portal
Publication:414866
DOI10.1016/j.jcss.2011.02.001zbMath1242.68124MaRDI QIDQ414866
Stefan Szeider, Luke Mathieson
Publication date: 11 May 2012
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2011.02.001
computational complexity; parameterized complexity; kernelization; graph editing; general factor; regular subgraph
68Q25: Analysis of algorithms and problem complexity
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Graph Editing to a Given Degree Sequence, Win-win kernelization for degree sequence completion problems, Prices matter for the parameterized complexity of shift bribery, Tight complexity bounds for FPT subgraph problems parameterized by the clique-width, Parameterized complexity of three edge contraction problems with degree constraints, Circulant graphs and GCD and LCM of subsets, Graph editing to a given degree sequence, Graph editing problems with extended regularity constraints, Editing to a planar graph of given degrees, Editing to Eulerian graphs, Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming, A refined complexity analysis of degree anonymization in graphs, Editing to a graph of given degrees, Editing to a connected graph of given degrees, The complexity of degree anonymization by graph contractions, Fixed-parameter tractable distances to sparse graph classes, Parameterized complexity of firefighting, Almost Induced Matching: Linear Kernels and Parameterized Algorithms, Editing to a Planar Graph of Given Degrees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of regular subgraph recognition
- On the fixed-parameter tractability of parameterized model-checking problems
- 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
- General factors of graphs
- Matching theory
- NP-completeness of some generalizations of the maximum matching problem
- Graph factors
- Induced matchings
- Deciding whether a planar graph has a cubic subgraph is NP-complete
- General antifactors of graphs
- On locating cubic subgraphs in bounded-degree connected bipartite graphs
- Antifactors of graphs
- Finding a \(\Delta\)-regular supergraph of minimum order
- Spanning subgraphs with specified valencies
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Finding regular subgraphs in both arbitrary and planar graphs
- Maximum \(k\)-regular induced subgraphs
- Parametrized complexity theory.
- Tight lower bounds for certain parameterized NP-hard problems
- Deciding first-order properties of locally tree-decomposable structures
- Kernels: Annotated, Proper and Induced
- An algorithmic proof of Tutte's f-factor theorem
- Paths, Trees, and Flowers
- Parameterized Graph Editing with Chosen Vertex Degrees
- The factorization of graphs. II
- A Short Proof of the Factor Theorem for Finite Graphs
- Three‐regular subgraphs of four‐regular graphs
- Combinatorial optimization. Theory and algorithms.
