Kernelization of Two Path Searching Problems on Split Graphs

DOI10.1007/978-3-319-39817-4_23zbMath1475.68255OpenAlexW2489997067MaRDI QIDQ4632190

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

Publication date: 26 April 2019

Published in: Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-39817-4_23

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Parameterized complexity, tractability and kernelization (68Q27)

Related Items

On the kernelization of split graph problems

Cites Work

• Unnamed Item
• Unnamed Item
• Planar graph vertex partition for linear problem kernels
• Finding disjoint paths in split graphs
• Kernel bounds for disjoint cycles and disjoint paths
• Turing kernelization for finding long paths and cycles in restricted graph classes
• Short cycles make \(W\)-hard problems hard: FPT algorithms for \(W\)-hard problems in graphs with no short cycles
• A kernelization algorithm for \(d\)-hitting set
• On problems without polynomial kernels
• Global wire routing in two-dimensional arrays
• Split graphs
• Graph minors. XIII: The disjoint paths problem
• HAMILTONian circuits in chordal bipartite graphs
• Towards optimal kernel for edge-disjoint triangle packing
• Crown structures for vertex cover kernelization
• Cutwidth of Split Graphs and Threshold Graphs
• Parameterized and Exact Computation
• Graph-Theoretic Concepts in Computer Science