Source author record

Inmaculada Ventura

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Discrete Mathematics

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Algorithms for the Euclidean Bipartite Edge Cover Problem

Given a graph $G=(V,E)$ with costs on its edges, the minimum-cost edge cover problem consists of finding a subset of $E$ covering all vertices in $V$ at minimum cost. If $G$ is bipartite, this problem can be solved in time $O(|V|^3)$ via a well-known reduction to a maximum-cost matching problem on $G$ . If in addition $V$ is a set of points on the Euclidean line, Collanino et al. showed that the problem can be solved in time $O(|V| \log |V|)$ and asked whether it can be solved in time $o(|V|^3)$ if $V$ is a set of points on the Euclidean plane. We answer this in the affirmative, giving an $O(|V|^{2.5} \log |V|)$ algorithm based on the Hungarian method using weighted Voronoi diagrams. We also propose some 2-approximation algorithms and give experimental results of our implementations.

preprint2012arXiv

Locating a single facility and a high-speed line

In this paper we study a facility location problem in the plane in which a single point (facility) and a rapid transit line (highway) are simultaneously located in order to minimize the total travel time from the clients to the facility, using the $L_1$ or Manhattan metric. The rapid transit line is given by a segment with any length and orientation, and is an alternative transportation line that can be used by the clients to reduce their travel time to the facility. We study the variant of the problem in which clients can enter and exit the highway at any point. We provide an $O(n^3)$ -time algorithm that solves this variant, where $n$ is the number of clients. We also present a detailed characterization of the solutions, which depends on the speed given in the highway.

preprint2012arXiv

The 1-Center and 1-Highway problem

We study a variation of the 1-center problem in which, in addition to a single supply facility, we are allowed to locate a highway. This highway increases the transportation speed between any demand point and the facility. That is, given a set $S$ of points and $v>1$ , we are interested in locating the facility point $f$ and the highway $h$ that minimize the expression $\max_{p\in S}d_{h}(p,f)$ , where $d_h$ is the time needed to travel between $p$ and $f$ . We consider two types of highways ({\em freeways} and {\em turnpikes}) and study the cases in which the highway's length is fixed by the user (or can be modified to further decrease the transportation time).

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.