On the kernelization of split graph problems

DOI10.1016/j.tcs.2017.09.023zbMath1393.68083OpenAlexW2759324182MaRDI QIDQ2636501

Jiong Guo, Yash Raj Shrestha, Wenjun Li, Yongjie Yang

Publication date: 5 June 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.09.023

zbMATH Keywords

split graph\(k\)-pathparameterized complexitykernelizationcrown decomposition\(k\)-cycle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Planar graph vertex partition for linear problem kernels
• Fundamentals of parameterized complexity
• The efficiency and stability of R\&D networks
• Finding disjoint paths in split graphs
• Kernel bounds for disjoint cycles and disjoint paths
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Complexity and kernels for bipartition into degree-bounded induced graphs
• Turing kernelization for finding long paths and cycles in restricted graph classes
• Obtaining split graphs by edge contraction
• A kernelization algorithm for \(d\)-hitting set
• Parameterizing above or below guaranteed values
• On problems without polynomial kernels
• Global wire routing in two-dimensional arrays
• Independent domination in chordal graphs
• Some simplified NP-complete graph problems
• Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
• Graph minors. XIII: The disjoint paths problem
• HAMILTONian circuits in chordal bipartite graphs
• Faster parameterized algorithms for deletion to split graphs
• Towards optimal kernel for edge-disjoint triangle packing
• Crown structures for vertex cover kernelization
• Parametrized complexity theory.
• Hitting Forbidden Minors: Approximation and Kernelization
• Cutwidth of Split Graphs and Threshold Graphs
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
• Graph Classes: A Survey
• Nestedness in networks: A theoretical model and some applications
• Kernelization of Two Path Searching Problems on Split Graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Parameterized and Exact Computation
• The Parameterized Complexity of k-B<scp>iclique</scp>
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: On the kernelization of split graph problems