Win-win kernelization for degree sequence completion problems

DOI10.1016/J.JCSS.2016.03.009MaRDI QIDQ295647zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational complexitydata reductionNP-hardness\(f\)-factorslower bounds for problem kernelspolynomial problem kernels

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Win-win kernelization for degree sequence completion problems
• Two edge modification problems without polynomial kernels
• Two edge modification problems without polynomial kernels
• Graph editing to a given degree sequence
• Editing to a planar graph of given degrees

Cites work

• scientific article; zbMATH DE number 3648761 (Why is no real title available?)
• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 4162938 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1467781 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• (Meta) Kernelization
• A Note on Unigraphic Sequences
• A generalization of Nemhauser and Trotter's local optimization theorem
• A refined complexity analysis of degree anonymization in graphs
• Advice classes of parametrized tractability
• Complexity classification of some edge modification problems
• Editing graphs to satisfy degree constraints: a parameterized approach
• Editing to a connected graph of given degrees
• Finding large degree-anonymous subgraphs is hard
• Fixed-parameter tractability of graph modification problems for hereditary properties
• Fundamentals of parameterized complexity
• General factors of graphs
• Graph Classes: A Survey
• Graph-Theoretic Concepts in Computer Science
• Kernel bounds for disjoint cycles and disjoint paths
• Kernelization Lower Bounds by Cross-Composition
• Linear recognition of pseudo-split graphs
• Matching theory
• New races in parameterized algorithmics
• Parameterized complexity of finding regular induced subgraphs
• Parametrized complexity theory.
• Recent developments in kernelization: a survey
• Recognition of unigraphs through superposition of graphs
• The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
• The splittance of a graph

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)