Editing graphs to satisfy degree constraints: a parameterized approach
From MaRDI portal
Publication:414866
DOI10.1016/J.JCSS.2011.02.001zbMATH Open1242.68124OpenAlexW2081215656MaRDI QIDQ414866FDOQ414866
Authors: 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
Recommendations
computational complexityparameterized complexitykernelizationgraph editinggeneral factorregular subgraph
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)
Cites Work
- Title not available (Why is that?)
- Matching theory
- Kernels: Annotated, Proper and Induced
- Paths, Trees, and Flowers
- Parameterized complexity of finding regular induced subgraphs
- Maximum \(k\)-regular induced subgraphs
- Parametrized complexity theory.
- Title not available (Why is that?)
- Combinatorial optimization. Theory and algorithms.
- Title not available (Why is that?)
- Title not available (Why is that?)
- Induced matchings
- On the parameterized complexity of multiple-interval graph problems
- General factors of graphs
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- A Short Proof of the Factor Theorem for Finite Graphs
- Graph factors
- Deciding first-order properties of locally tree-decomposable structures
- NP-completeness of some generalizations of the maximum matching problem
- Tight lower bounds for certain parameterized NP-hard problems
- Deciding whether a planar graph has a cubic subgraph is NP-complete
- On locating cubic subgraphs in bounded-degree connected bipartite graphs
- Finding regular subgraphs in both arbitrary and planar graphs
- Three‐regular subgraphs of four‐regular graphs
- The complexity of regular subgraph recognition
- A note on the complexity of finding regular subgraphs
- General antifactors of graphs
- Antifactors of graphs
- Finding a \(\Delta\)-regular supergraph of minimum order
- Spanning subgraphs with specified valencies
- An algorithmic proof of Tutte's f-factor theorem
- Parameterized Graph Editing with Chosen Vertex Degrees
- The factorization of graphs. II
- On the fixed-parameter tractability of parameterized model-checking problems
Cited In (35)
- Editing graphs to satisfy diversity requirements
- Temporal reachability minimization: delaying vs. deleting
- Editing to a connected graph of given degrees
- A parameterized algorithmics framework for degree sequence completion problems in directed graphs
- Parameterized Graph Editing with Chosen Vertex Degrees
- Almost induced matching: linear kernels and parameterized algorithms
- The complexity of degree anonymization by graph contractions
- An improved linear kernel for the cycle contraction problem
- Fixed-parameter tractable distances to sparse graph classes
- Parameterized algorithms and kernels for almost induced matching
- Win-win kernelization for degree sequence completion problems
- How hard is safe bribery?
- Parameterized complexity of firefighting
- A survey of parameterized algorithms and the complexity of edge modification
- Prices matter for the parameterized complexity of shift bribery
- Building large \(k\)-cores from sparse graphs
- Building large \(k\)-cores from sparse graphs
- Parameterized complexity of three edge contraction problems with degree constraints
- Disconnected matchings
- The complexity of gerrymandering over graphs: paths and trees
- The complexity of gerrymandering over graphs: paths and trees
- Circulant graphs and GCD and LCM of subsets
- An improved kernel and parameterized algorithm for almost induced matching
- The parameterized complexity of editing graphs for bounded degeneracy
- Graph editing to a given degree sequence
- Graph editing to a given degree sequence
- Trimming forests is hard (unless they are made of stars)
- Editing to Eulerian graphs
- A refined complexity analysis of degree anonymization in graphs
- Editing to Connected F-Degree Graph
- Editing to a planar graph of given degrees
- Editing to a planar graph of given degrees
- Graph editing to a given neighbourhood degree list is fixed-parameter tractable
- Tight complexity bounds for FPT subgraph problems parameterized by the clique-width
- Graph editing problems with extended regularity constraints
This page was built for publication: Editing graphs to satisfy degree constraints: a parameterized approach
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414866)
