1 citations · 2 across the 9 of their papers we have counts for
4 papers · 1 filter
Minimum Sum Vertex Cover via Minimum Vertex Cover
Ahmad Biniaz, Jean-Lou De Carufel, Anil Maheshwari +2
The Minimum Sum Vertex Cover (MSVC) problem asks for an ordering of the vertices of a graph that minimizes the sum, over all edges, of the time at which each edge is first covered.…
On 2-Layer k-Matching-Planar Graphs
Saeed Odak, Jonathan Rollin, Torben Scheele
A graph is -matching-planar if it admits a drawing in the plane such that, for every edge , the edges crossing contain no matching of size greater than . The class of…
Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes
Manuel Cáceres, Sándor Kisfaludi-Bak, Saeed Odak
The shifting technique of Hochbaum and Maass [J.ACM'85] produces PTASes with the fastest known running times for several -dimensional geometric prob…
Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
Sándor Kisfaludi-Bak, Saeed Odak, Satyam Singh +1
We give an approximation scheme for the TSP in -dimensional hyperbolic space that has optimal dependence on under Gap-ETH. For any fixed dimension and fo…