Source author record

Yann Vaxès

Yann Vaxès appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Geometry Discrete Mathematics math.CO Distributed, Parallel, and Cluster Computing math.MG

Catalog footprint

What is connected

7works

6topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2022arXiv

Optimizing the ecological connectivity of landscapes with generalized flow models and preprocessing

In this paper we consider the problem of optimizing the ecological connectivity of a landscape under a budget constraint by improving habitat areas and ecological corridors between them. We consider a formulation of this problem in terms of graphs in which vertices represent the habitat areas and arcs represent a probability of connection between two areas that depend on the quality of the respective corridor. We propose a new generalized flow model that improves existing models for this problem and an efficient preprocessing algorithm that reduces the size of the graphs on which generalized flows is computed. Reported numerical experiments highlight the benefice of these two contributions on computation times and show that larger problems can be solved using them. Our experiments also show that several variants of greedy algorithms perform relatively well on practical instances while they return arbitrary bad solutions in the worst case.

preprint2020arXiv

Medians in median graphs and their cube complexes in linear time

The median of a set of vertices $P$ of a graph $G$ is the set of all vertices $x$ of $G$ minimizing the sum of distances from $x$ to all vertices of $P$. In this paper, we present a linear time algorithm to compute medians in median graphs, improving over the existing quadratic time algorithm. We also present a linear time algorithm to compute medians in the $\ell_1$-cube complexes associated with median graphs. Median graphs constitute the principal class of graphs investigated in metric graph theory and have a rich geometric and combinatorial structure, due to their bijections with CAT(0) cube complexes and domains of event structures. Our algorithm is based on the majority rule characterization of medians in median graphs and on a fast computation of parallelism classes of edges ($Θ$-classes or hyperplanes) via Lexicographic Breadth First Search (LexBFS). To prove the correctness of our algorithm, we show that any LexBFS ordering of the vertices of $G$ satisfies the following fellow traveler property of independent interest: the parents of any two adjacent vertices of $G$ are also adjacent. Using the fast computation of the $Θ$-classes, we also compute the Wiener index (total distance) of $G$ in linear time and the distance matrix in optimal quadratic time.

preprint2016arXiv

Convergecast and Broadcast by Power-Aware Mobile Agents

A set of identical, mobile agents is deployed in a weighted network. Each agent has a battery -- a power source allowing it to move along network edges. An agent uses its battery proportionally to the distance traveled. We consider two tasks : convergecast, in which at the beginning, each agent has some initial piece of information, and information of all agents has to be collected by some agent; and broadcast in which information of one specified agent has to be made available to all other agents. In both tasks, the agents exchange the currently possessed information when they meet. The objective of this paper is to investigate what is the minimal value of power, initially available to all agents, so that convergecast or broadcast can be achieved. We study this question in the centralized and the distributed settings. In the centralized setting, there is a central monitor that schedules the moves of all agents. In the distributed setting every agent has to perform an algorithm being unaware of the network. In the centralized setting, we give a linear-time algorithm to compute the optimal battery power and the strategy using it, both for convergecast and for broadcast, when agents are on the line. We also show that finding the optimal battery power for convergecast or for broadcast is NP-hard for the class of trees. On the other hand, we give a polynomial algorithm that finds a 2-approximation for convergecast and a 4-approximation for broadcast, for arbitrary graphs. In the distributed setting, we give a 2-competitive algorithm for convergecast in trees and a 4-competitive algorithm for broadcast in trees. The competitive ratio of 2 is proved to be the best for the problem of convergecast, even if we only consider line networks. Indeed, we show that there is no (2 -- $ε$)-competitive algorithm for convergecast or for broadcast in the class of lines, for any $ε$ \textgreater{} 0.

preprint2016arXiv

Core congestion is inherent in hyperbolic networks

We investigate the impact the negative curvature has on the traffic congestion in large-scale networks. We prove that every Gromov hyperbolic network $G$ admits a core, thus answering in the positive a conjecture by Jonckheere, Lou, Bonahon, and Baryshnikov, Internet Mathematics, 7 (2011) which is based on the experimental observation by Narayan and Saniee, Physical Review E, 84 (2011) that real-world networks with small hyperbolicity have a core congestion. Namely, we prove that for every subset $X$ of vertices of a $δ$-hyperbolic graph $G$ there exists a vertex $m$ of $G$ such that the disk $D(m,4 δ)$ of radius $4 δ$ centered at $m$ intercepts at least one half of the total flow between all pairs of vertices of $X$, where the flow between two vertices $x,y\in X$ is carried by geodesic (or quasi-geodesic) $(x,y)$-paths. A set $S$ intercepts the flow between two nodes $x$ and $y$ if $S$ intersect every shortest path between $x$ and $y$. Differently from what was conjectured by Jonckheere et al., we show that $m$ is not (and cannot be) the center of mass of $X$ but is a node close to the median of $X$ in the so-called injective hull of $X$. In case of non-uniform traffic between nodes of $X$ (in this case, the unit flow exists only between certain pairs of nodes of $X$ defined by a commodity graph $R$), we prove a primal-dual result showing that for any $ρ>5δ$ the size of a $ρ$-multi-core (i.e., the number of disks of radius $ρ$) intercepting all pairs of $R$ is upper bounded by the maximum number of pairwise $(ρ-3δ)$-apart pairs of $R$.

preprint2010arXiv

Cop and robber games when the robber can hide and ride

In the classical cop and robber game, two players, the cop C and the robber R, move alternatively along edges of a finite graph G. The cop captures the robber if both players are on the same vertex at the same moment of time. A graph G is called cop win if the cop always captures the robber after a finite number of steps. Nowakowski, Winkler (1983) and Quilliot (1983) characterized the cop-win graphs as graphs admitting a dismantling scheme. In this paper, we characterize in a similar way the class CW(s,s') of cop-win graphs in the game in which the cop and the robber move at different speeds s' and s, s'<= s. We also establish some connections between cop-win graphs for this game with s'<s and Gromov's hyperbolicity. In the particular case s'=1 and s=2, we prove that the class of cop-win graphs is exactly the well-known class of dually chordal graphs. We show that all classes CW(s,1), s>=3, coincide and we provide a structural characterization of these graphs. We also investigate several dismantling schemes necessary or sufficient for the cop-win graphs in the game in which the robber is visible only every k moves for a fixed integer k>1. We characterize the graphs which are cop-win for any value of k. Finally, we consider the game where the cop wins if he is at distance at most 1 from the robber and we characterize via a specific dismantling scheme the bipartite graphs where a single cop wins in this game.

preprint2010arXiv

Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm

Let B be a centrally symmetric convex polygon of R^2 and || p - q || be the distance between two points p,q in R^2 in the normed plane whose unit ball is B. For a set T of n points (terminals) in R^2, a B-Manhattan network on T is a network N(T) = (V,E) with the property that its edges are parallel to the directions of B and for every pair of terminals t_i and t_j, the network N(T) contains a shortest B-path between them, i.e., a path of length || t_i - t_j ||. A minimum B-Manhattan network on T is a B-Manhattan network of minimum possible length. The problem of finding minimum B-Manhattan networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX'99) in the case when the unit ball B is a square (and hence the distance || p - q || is the l_1 or the l_infty-distance between p and q) and it has been shown recently by Chin, Guo, and Sun (SoCG'09) to be strongly NP-complete. Several approximation algorithms (with factors 8, 4 ,3 , and 2) for minimum Manhattan problem are known. In this paper, we propose a factor 2.5 approximation algorithm for minimum B-Manhattan network problem. The algorithm employs a simplified version of the strip-staircase decomposition proposed in our paper (APPROX'05) and subsequently used in other factor 2 approximation algorithms for minimum Manhattan problem.

preprint2009arXiv

Embedding into the rectilinear plane in optimal O*(n^2)

We present an optimal O*(n^2) time algorithm for deciding if a metric space (X,d) on n points can be isometrically embedded into the plane endowed with the l_1-metric. It improves the O*(n^2 log^2 n) time algorithm of J. Edmonds (2008). Together with some ingredients introduced by J. Edmonds, our algorithm uses the concept of tight span and the injectivity of the l_1-plane. A different O*(n^2) time algorithm was recently proposed by D. Eppstein (2009).