Win-win kernelization for degree sequence completion problems
From MaRDI portal
Publication:295647
DOI10.1016/j.jcss.2016.03.009zbMath1345.68156MaRDI QIDQ295647
Rolf Niedermeier, André Nichterlein, Vincent Froese
Publication date: 13 June 2016
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.2016.03.009
computational complexity; data reduction; NP-hardness; \(f\)-factors; lower bounds for problem kernels; polynomial problem kernels
68Q25: Analysis of algorithms and problem complexity
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
A survey of parameterized algorithms and the complexity of edge modification, Editing to a planar graph of given degrees, A parameterized algorithmics framework for degree sequence completion problems in directed graphs, Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Editing graphs to satisfy degree constraints: a parameterized approach
- Kernel bounds for disjoint cycles and disjoint paths
- A generalization of Nemhauser and Trotter's local optimization theorem
- Advice classes of parametrized tractability
- Parameterized complexity of finding regular induced subgraphs
- General factors of graphs
- Matching theory
- The splittance of a graph
- Linear recognition of pseudo-split graphs
- Fixed-parameter tractability of graph modification problems for hereditary properties
- A refined complexity analysis of degree anonymization in graphs
- Editing to a graph of given degrees
- Parametrized complexity theory.
- Recognition of Unigraphs through Superposition of Graphs
- New Races in Parameterized Algorithmics
- Editing to a Connected Graph of Given Degrees
- The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
- A Note on Unigraphic Sequences
- Graph Classes: A Survey
- Kernelization Lower Bounds by Cross-Composition
- (Meta) Kernelization
- Graph-Theoretic Concepts in Computer Science
- Complexity classification of some edge modification problems
- Finding large degree-anonymous subgraphs is hard