Editing to a graph of given degrees
From MaRDI portal
Publication:2354405
DOI10.1016/j.tcs.2015.04.034zbMath1322.68142arXiv1311.4768OpenAlexW1577575477MaRDI QIDQ2354405
Publication date: 13 July 2015
Published in: Theoretical Computer Science, Parameterized and Exact Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1311.4768
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)
Related Items (13)
Win-win kernelization for degree sequence completion problems ⋮ Editing to a Planar Graph of Given Degrees ⋮ Fixed-parameter tractable distances to sparse graph classes ⋮ Editing to Eulerian graphs ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ 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 ⋮ Graph Editing to a Given Degree Sequence ⋮ Unnamed Item ⋮ Editing to a planar graph of given degrees ⋮ Finding large degree-anonymous subgraphs is hard ⋮ Editing to a graph of given degrees
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Editing graphs to satisfy degree constraints: a parameterized approach
- Parameterized complexity of even/odd subgraph problems
- Parameterized complexity of finding regular induced subgraphs
- The node-deletion problem for hereditary properties is NP-complete
- A trinomial analogue of Bailey's lemma and \(N=2\) superconformal invariance
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Parameterized complexity of finding subgraphs with hereditary properties.
- Editing to a graph of given degrees
- Additive approximation for edge-deletion problems
- Parametrized complexity theory.
- NP-completeness results for edge modification problems
- Editing to a Connected Graph of Given Degrees
- Parameterized Complexity of Eulerian Deletion Problems
- Win-Win Kernelization for Degree Sequence Completion Problems
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Color-coding
- Kernelization Lower Bounds by Cross-Composition
- Node-and edge-deletion NP-complete problems
- Complexity classification of some edge modification problems
This page was built for publication: Editing to a graph of given degrees
