Showing 2024Show all
3 papers · 1 filter
cs.DS2024
A Simplified Parameterized Algorithm for Directed Feedback Vertex Set
Ziliang Xiong, Mingyu Xiao
The Directed Feedback Vertex Set problem (DFVS) asks whether it is possible to remove at most vertices from a directed graph to make it acyclic. Whether DFVS is fixed-parameter…
cs.DS2024
The Traveling Tournament Problem: Improved Algorithms Based on Cycle Packing
Jingyang Zhao, Mingyu Xiao, Chao Xu
The Traveling Tournament Problem (TTP) is a well-known benchmark problem in the field of tournament timetabling, which asks us to design a double round-robin schedule such that eac…
cs.DS2024
An Improved Approximation Algorithm for Metric Triangle Packing
Jingyang Zhao, Mingyu Xiao
Given an edge-weighted metric complete graph with vertices, the maximum weight metric triangle packing problem is to find a set of vertex-disjoint triangles with the tota…