检索结果-南通市图书馆

Improved kernels for triangle packing in tournaments

Science China(Information Sciences) 2023年第5期66卷 100-113页

作者： Hanchun YUAN Qilong FENG Jianxin WANG School of Computer Science and Engineering Central South University Hunan Provincial Key Lab on Bioinformatics Central South University

Triangle packing problem has been paid lots of attention to in the literature. In this paper, we study the kernelization of the triangle packing problem in tournaments. For the parameterized arc-disjoint triangle packing problem in tournaments, we find a maximal arc-disjoint triangle packing with the number of vertices bounded by 2.5k. Based on the relation between the maximal arc-disjoint triangle packing and the vertices outside of the packing, a kernel of size 3.5k for the problem is obtained, improving the previous best one 6k. For the parameterized vertex-disjoint triangle packing problem in sparse tournaments, several new properties between the triangles in maximal vertex-disjoint triangle packing and the arcs in the feedback arc set are presented, which result in a kernel of size 7k for the problem, improving the previous best one of 15k.We also give a 7k vertex kernel for the parameterized feedback vertex set problem in sparse tournaments.The kernelization process presented in this paper for the parameterized arc-disjoint triangle packing can be applied to solve the parameterized arc-disjoint triangle packing problem on other restricted directed graph classes.

关键词： tournaments triangle packing kernelization fixed-parameter tractable graph algorithms

来源：

同方期刊数据库评论

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

2k-Vertex Kernels for Cluster Deletion and Strong Triadic Closure

引用

Journal of Computer Science & Technology 2023年第6期38卷 1431-1439页

作者：高文宇高航 School of Information Guangdong University of Finance and EconomicsGuangzhou 510320China Department of Computer Science Rutgers UniversityPiscataway 08854U.S.A.

Cluster deletion and strong triadic closure are two important NP-complete problems that have received sig-nificant attention due to their applications in various areas,including social networks and data analysis.Although cluster deletion and strong triadic closure are closely linked by induced paths on three vertices,there are subtle differences be-tween them.In some cases,the solutions of strong triadic closure and cluster deletion are quite different.In this paper,we study the parameterized algorithms for these two problems.More specifically,we focus on the kernels of these two prob-lems.Instead of separating the critical clique and its neighbors for analysis,we consider them as a whole,which allows us to more effectively bound the number of related vertices.In addition,in analyzing the kernel of strong triadic closure,we introduce the concept of edge-disjoint induced path on three vertices,which enables us to obtain the lower bound of weak edge number in a more concise way.Our analysis demonstrates that cluster deletion and strong triadic closure both admit 2k-vertex kernels.These results represent improvements over previously best-known kernels for both problems.Further-more,our analysis provides additional insights into the relationship between cluster deletion and strong triadic closure.

关键词： cluster deletion strong triadic closure kernelization parameterized complexity social network

来源：

维普期刊数据库评论

在线全文

维普期刊数据库

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：