SEARA , Carlos

This paper initiates a study on the problem of computing the difference between the metric dimension and the determining number of graphs. We provide new proofs and results on the determining number of trees and Cartesian products of graphs, and establish some lower bounds on the difference between the two parameters.

We undertake a study on computing Hamiltonian alternating cycles and paths on bicolored point sets. This has been an intensively studied problem, not always with a solution, when the paths and cycles are also required to be plane. In this paper, we relax the constraint on the cycles and paths from being plane to being 1-plane, and deal with the...

En este trabajo estudiamos el problema de determinar si dos conjuntos disjuntos de n puntos en el plano son separables mediante una estructura de 2-level tree, compuesta por una recta y dos semirrectas, y diseñamos algoritmos óptimos de tiempo £(n log n) para resolver este problema.

Given linearly inseparable sets R of red points and B of blue points, we consider several measures of how far they are from being separable. Intuitively, given a potential separator (''classifier''), we measure its quality (''error'') according to how much work it would take to move the misclassified points across the classifier to yield...

Given a finite set of weighted points in Rd (where there can be negative weights), the maximum box problem asks for an axis-aligned rectangle (i.e., box) such that the sum of the weights of the points that it contains is maximized. We consider that each point of the input has a probability of being present in the final random point set, and...