Nestaly Marín

collaborators

2 papers

cs.CG2025

The Euclidean $k$ -Matching Problem is NP-hard

José-Miguel Díaz-Báñez, Ruy Fabila-Monroy, José-Manuel Higes-López +3

Let $G$ be a complete edge-weighted graph on $n$ vertices. To each subset of vertices of $G$ assign the cost of the minimum spanning tree of the subset as its weight. Suppose that…

cs.CG2024

An efficient algorithm for identifying rainbow ortho-convex 4-sets in k-colored point sets

David Flores-Peñaloza, Mario A. Lopez, Nestaly Marín +1

Let $P$ be a $k$ -colored set of $n$ points in the plane, $4 \leq k \leq n$ . We study the problem of deciding if $P$ contains a subset of four points of different colors such that i…

The Euclidean k-Matching Problem is NP-hard

An efficient algorithm for identifying rainbow ortho-convex 4-sets in k-colored point sets

The Euclidean $k$ -Matching Problem is NP-hard