标题:Kernelization of Two Path Searching Problems on Split Graphs
作者:Yang, Yongjie; Shrestha, Yash Raj; Li, Wenjun; Guo, Jiong
通讯作者:Guo, Jiong
作者机构:[Yang, Yongjie] Univ Saarbrucken, Saarbrucken, Germany.; [Shrestha, Yash Raj] ETH, Dept Management Technol & Econ, Zurich, Switzerland.; [Li, Wenj 更多
会议名称:10th International Frontiers of Algorithmics Workshop (FAW)
会议日期:JUN 30-JUL 02, 2016
来源:Frontiers in Algorithmics, FAW 2016
出版年:2016
卷:9711
页码:238-249
DOI:10.1007/978-3-319-39817-4_23
摘要:In the k-Vertex-Disjoint Paths problem, we are given a graph G and k terminal pairs of vertices, and are asked whether there is a set of k vertex-disjoint paths linking these terminal pairs, respectively. In the k-Path problem, we are given a graph and are asked whether there is a path of length k. It is known that both problems are NP-hard even in split graphs, which are the graphs whose vertices can be partitioned into a clique and an independent set. We study kernelization for the two problems in split graphs. In particular, we derive a 4k vertex-kernel for the k-Vertex-Disjoint Paths problem and a 3/2k(2) + 1/2k vertex-kernel for the k-Path problem.
收录类别:CPCI-S;EI;SCOPUS
WOS核心被引频次:1
Scopus被引频次:1
资源类型:会议论文;期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84976626484&doi=10.1007%2f978-3-319-39817-4_23&partnerID=40&md5=b2b2742a5c6d42ef0b5a1e07518792e6
TOP