49 citations · 62 across the 16 of their papers we have counts for
3 papers · 1 filter
Diameter and Length of Metric Graphs
Hee-Kap Ahn, Sergio Cabello, Otfried Cheong +2
A metric graph is a metric space obtained from a finite collection of intervals whose endpoints are identified in groups. It can also be seen as a finite, edge-weighted graph where…
The Borsuk number of a graph
José Cáceres, Delia Garijo, Alberto Márquez +1
The Borsuk problem asks for the smallest number of subsets with strictly smaller diameters into which any bounded set in the -dimensional space can be decomposed. It is a classi…
On the complexity of covering points by guillotine cuts
Delia Garijo, Alberto Márquez, Rodrigo I. Silveira
We show that the problem of covering a set of points in the plane with a minimum number of guillotine cuts is NP-complete. To that end, first we present a new NP-completeness proof…