4 papers
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…
PTAS for Steiner Tree on Map Graphs
Jarosław Byrka, Mateusz Lewandowski, Syed Mohammad Meesum +2
We study the Steiner tree problem on map graphs, which substantially generalize planar graphs as they allow arbitrarily large cliques. We obtain a PTAS for Steiner tree on map grap…
A Tight Approximation for Submodular Maximization with Mixed Packing and Covering Constraints
Eyal Mizrachi, Roy Schwartz, Joachim Spoerhase +1
Motivated by applications in machine learning, such as subset selection and data summarization, we consider the problem of maximizing a monotone submodular function subject to mixe…
A Tight Extremal Bound on the Lovász Cactus Number in Planar Graphs
Parinya Chalermsook, Andreas Schmid, Sumedha Uniyal
A cactus graph is a graph in which any two cycles are edge-disjoint. We present a constructive proof of the fact that any plane graph contains a cactus subgraph where c…