Win-win kernelization for degree sequence completion problems
DOI10.1016/J.JCSS.2016.03.009zbMATH Open1345.68156OpenAlexW2963877701MaRDI QIDQ295647FDOQ295647
Authors: Vincent Froese, André Nichterlein, Rolf Niedermeier 
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
Recommendations
computational complexitydata reductionNP-hardness\(f\)-factorslower bounds for problem kernelspolynomial problem kernels
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Fundamentals of parameterized complexity
- Title not available (Why is that?)
- Matching theory
- Fixed-parameter tractability of graph modification problems for hereditary properties
- Graph Classes: A Survey
- Parameterized complexity of finding regular induced subgraphs
- Parametrized complexity theory.
- Recent developments in kernelization: a survey
- Title not available (Why is that?)
- A generalization of Nemhauser and Trotter's local optimization theorem
- Title not available (Why is that?)
- Kernelization Lower Bounds by Cross-Composition
- (Meta) Kernelization
- Linear recognition of pseudo-split graphs
- The splittance of a graph
- General factors of graphs
- A refined complexity analysis of degree anonymization in graphs
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Note on Unigraphic Sequences
- Editing graphs to satisfy degree constraints: a parameterized approach
- Title not available (Why is that?)
- Graph-Theoretic Concepts in Computer Science
- Complexity classification of some edge modification problems
- Finding large degree-anonymous subgraphs is hard
- Kernel bounds for disjoint cycles and disjoint paths
- Advice classes of parametrized tractability
Cited In (5)
- Parameterized Algorithmics for Graph Modification Problems: On Interactions with Heuristics
- A parameterized algorithmics framework for degree sequence completion problems in directed graphs
- A survey of parameterized algorithms and the complexity of edge modification
- Win-win kernelization for degree sequence completion problems
- Editing to a planar graph of given degrees
This page was built for publication: Win-win kernelization for degree sequence completion problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q295647)
