Editing graphs to satisfy degree constraints: a parameterized approach
From MaRDI portal
Publication:414866
DOI10.1016/j.jcss.2011.02.001zbMath1242.68124OpenAlexW2081215656MaRDI QIDQ414866
Luke Mathieson, Stefan Szeider
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 complexityparameterized complexitykernelizationgraph editinggeneral factorregular subgraph
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (30)
Disconnected matchings ⋮ Win-win kernelization for degree sequence completion problems ⋮ Almost Induced Matching: Linear Kernels and Parameterized Algorithms ⋮ Prices matter for the parameterized complexity of shift bribery ⋮ Editing to a Planar 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 ⋮ Tight complexity bounds for FPT subgraph problems parameterized by the clique-width ⋮ How hard is safe bribery? ⋮ Building large \(k\)-cores from sparse graphs ⋮ Editing to Eulerian graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Parameterized algorithms and kernels for almost induced matching ⋮ Parameterized complexity of three edge contraction problems with degree constraints ⋮ Parameterized complexity of firefighting ⋮ Circulant graphs and GCD and LCM of subsets ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ Graph editing to a given degree sequence ⋮ Graph editing problems with extended regularity constraints ⋮ Parameterized complexity results for general factors in bipartite graphs with an application to constraint programming ⋮ Graph Editing to a Given Degree Sequence ⋮ An improved linear kernel for the cycle contraction problem ⋮ Unnamed Item ⋮ Editing to a planar graph of given degrees ⋮ The complexity of gerrymandering over graphs: paths and trees ⋮ The complexity of gerrymandering over graphs: paths and trees ⋮ Editing to Connected F-Degree Graph ⋮ A refined complexity analysis of degree anonymization in graphs ⋮ Editing to a 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.
This page was built for publication: Editing graphs to satisfy degree constraints: a parameterized approach
