Asset Details
Do you wish to reserve the book?
Improved kernels for triangle packing in tournaments
Hey, we have placed the reservation for you!
By the way, why not check out events that you can attend while you pick your title.
Oops! Something went wrong.
Looks like we were not able to place the reservation. Kindly try again later.
Are you sure you want to remove the book from the shelf?
Improved kernels for triangle packing in tournaments
Do you wish to request the book?
Improved kernels for triangle packing in tournaments
Please be aware that the book you have requested cannot be checked out. If you would like to checkout this book, you can reserve another copy
We have requested the book for you!
Your request is successful and it will be processed during the Library working hours. Please check the status of your request in My Requests.
Oops! Something went wrong.
Looks like we were not able to place your request. Kindly try again later.
Journal Article
Improved kernels for triangle packing in tournaments
2023
Overview
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.5
k
. Based on the relation between the maximal arc-disjoint triangle packing and the vertices outside of the packing, a kernel of size 3.5
k
for the problem is obtained, improving the previous best one 6
k
. 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 7
k
for the problem, improving the previous best one of 15
k
. We also give a 7
k
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.
Publisher
Science China Press,Springer Nature B.V
