3 papers
cs.DS2022
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai +3
In the -edge-connected spanning subgraph (ECSS) problem, our goal is to compute a minimum-cost sub-network that is resilient against up to link failures: Given an -nod…
cs.DS2021
Retraction: Improved Approximation Schemes for Dominating Set Problems in Unit Disk Graphs
Jittat Fakcharoenphol, Pattara Sukprasert
Retraction note: After posting the manuscript on arXiv, we were informed by Erik Jan van Leeuwen that both results were known and they appeared in his thesis[vL09]. A PTAS for MDS…
cs.DM2020
Multi-transversals for Triangles and the Tuza's Conjecture
Parinya Chalermsook, Samir Khuller, Pattara Sukprasert +1
In this paper, we study a primal and dual relationship about triangles: For any graph , let be the maximum number of edge-disjoint triangles in , and be the min…