52 citations · 118 across the 27 of their papers we have counts for
4 papers · 1 filter
Simple PTAS's for families of graphs excluding a minor
Sergio Cabello, David Gajser
We show that very simple algorithms based on local search are polynomial-time approximation schemes for Maximum Independent Set, Minimum Vertex Cover and Minimum Dominating Set, wh…
Peeling potatoes near-optimally in near-linear time
Sergio Cabello, Josef Cibulka, Jan Kynčl +2
We consider the following geometric optimization problem: find a convex polygon of maximum area contained in a given simple polygon with vertices. We give a randomized near…
Finding Largest Rectangles in Convex Polygons
Sergio Cabello, Otfried Cheong, Christian Knauer +1
We consider the following geometric optimization problem: find a maximum-area rectangle and a maximum-perimeter rectangle contained in a given convex polygon with vertices. We…
Shortest Paths in Intersection Graphs of Unit Disks
Sergio Cabello, Miha Jejčič
Let be a unit disk graph in the plane defined by disks whose positions are known. For the case when is unweighted, we give a simple algorithm to compute a shortest path…