Algorithms and Logic Group

Kernels for Planar Vertex-Disjoint Triangle Packing

Seminars · Weekly Seminars
Speaker
Zimo Sheng
Affiliation
University of Electronic and Science Technology of China
Date
Time
– Asia/Shanghai
Venue
Main Building

Abstract

Triangle Packing is an important class of NP-hard problem. In this paper, we study Parameterized Planar Vertex-Disjoint Triangle Packing problem, which is to find $k$ vertex-disjoint triangles in a given planar graph. The current best kernel for this problem is $732k$. In this paper we will improve the result to $150k$ by giving new reduction rules and more careful analyze.

Schedule

  • 10:00-12:00 (Time in Beijing)
  • 14:00-16:00 (Time in Auckland)
  • May 14, 2021 (Friday)

Online Meeting

Link: https://meeting.tencent.com/s/oLdo3h9nEQlW

ID: 655 461 488