Yann Vaxès
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Yann Vaxès has a total of 16 co-authors. Here are the top co-authors by number of shared publications:
- Victor Chepoi
Faculté des Sciences de Luminy Laboratoire d'Informatique Fondamentale Université d'Aix-Marseille F-13288 Marseille Cedex 9 France
13 shared publications - Feodor F. Dragan
Department of Computer Science, Kent State University, Kent, USA
5 shared publications - Bertrand Estellon
Université de la Mediterranée, Marseille
4 shared publications - Karim Nouioua
Aix-Marseille Universite
4 shared publications - Nicolas Catusse
Aix-Marseille Universite
3 shared publications - Emmanuel Godard
Aix-Marseille Universite
1 shared publication
Latest Publications
- 23 November 2011
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 47 (1) , 187-214
Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs
- 23 November 2011
- Published by Springer Nature in Discrete & Computational Geometry
- Vol. 47 (1) , 187-214
Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs
- 31 August 2011
- Published by Springer Nature in Algorithmica
- Vol. 63 (1-2) , 551-567
Minimum Manhattan Network Problem in Normed Planes with Polygonal Balls: A Factor 2.5 Approximation Algorithm
- 31 August 2011
- Published by Springer Nature in Algorithmica
- Vol. 63 (1-2) , 551-567
Minimum Manhattan Network Problem in Normed Planes with Polygonal Balls: A Factor 2.5 Approximation Algorithm
- Open Access
Bidirected minimum Manhattan network problem
In the bidirected minimum Manhattan network problem, given a set T of n terminals in the plane, we need to construct a network N(T) of minimum total length with the property that the edges of N(T) are axis-parallel and oriented in a such a way that every ordered pair of terminals is connected in N(T) by a directed Manhattan path. In this paper, we present a polynomial factor 2 approximation algorithm for the bidirected minimum Manhattan network problem.
Open AccessBidirected minimum Manhattan network problem
In the bidirected minimum Manhattan network problem, given a set T of n terminals in the plane, we need to construct a network N(T) of minimum total length with the property that the edges of N(T) are axis-parallel and oriented in a such a way that every ordered pair of terminals is connected in N(T) by a directed Manhattan path. In this paper, we present a polynomial factor 2 approximation algorithm for the bidirected minimum Manhattan network problem.
- 24 December 2010
- Published by Springer Nature in Algorithmica
- Vol. 62 (3-4) , 713-732
Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs
- 24 December 2010
- Published by Springer Nature in Algorithmica
- Vol. 62 (3-4) , 713-732
Additive Spanners and Distance and Routing Labeling Schemes for Hyperbolic Graphs
- 28 September 2010
- Published by Springer Nature in Algorithmica
- Vol. 62 (1-2) , 146-168
A Self-stabilizing Algorithm for the Median Problem in Partial Rectangular Grids and Their Relatives
- 28 September 2010
- Published by Springer Nature in Algorithmica
- Vol. 62 (1-2) , 146-168
A Self-stabilizing Algorithm for the Median Problem in Partial Rectangular Grids and Their Relatives
- Open Access
Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
In this paper, we present a simple factor 6 algorithm for approximating the optimal multiplicative distortion of embedding a graph metric into a tree metric (thus improving and simplifying the factor 100 and 27 algorithms of B\v{a}doiu, Indyk, and Sidiropoulos (2007) and B\v{a}doiu, Demaine, Hajiaghayi, Sidiropoulos, and Zadimoghaddam (2008)). We also present a constant factor algorithm for approximating the optimal distortion of embedding a graph metric into an outerplanar metric. For this, we introduce a general notion of metric relaxed minor and show that if G contains an alpha-metric relaxed H-minor, then the distortion of any embedding of G into any metric induced by a H-minor free graph is at meast alpha. Then, for H=K_{2,3}, we present an algorithm which either finds an alpha-relaxed minor, or produces an O(alpha)-embedding into an outerplanar metric.
Open AccessConstant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
In this paper, we present a simple factor 6 algorithm for approximating the optimal multiplicative distortion of embedding a graph metric into a tree metric (thus improving and simplifying the factor 100 and 27 algorithms of B\v{a}doiu, Indyk, and Sidiropoulos (2007) and B\v{a}doiu, Demaine, Hajiaghayi, Sidiropoulos, and Zadimoghaddam (2008)). We also present a constant factor algorithm for approximating the optimal distortion of embedding a graph metric into an outerplanar metric. For this, we introduce a general notion of metric relaxed minor and show that if G contains an alpha-metric relaxed H-minor, then the distortion of any embedding of G into any metric induced by a H-minor free graph is at meast alpha. Then, for H=K_{2,3}, we present an algorithm which either finds an alpha-relaxed minor, or produces an O(alpha)-embedding into an outerplanar metric.
- Open Access
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).
Open AccessEmbedding 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).
- 23 July 2008
- Published by Elsevier in Theoretical Computer Science
- Vol. 401 (1-3) , 131-143
Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length
- 23 July 2008
- Published by Elsevier in Theoretical Computer Science
- Vol. 401 (1-3) , 131-143
Approximation algorithms for forests augmentation ensuring two disjoint paths of bounded length
- 12 October 2007
- Published by Elsevier in Theoretical Computer Science
- Vol. 390 (1) , 56-69
A rounding algorithm for approximating minimum Manhattan networks
- 12 October 2007
- Published by Elsevier in Theoretical Computer Science
- Vol. 390 (1) , 56-69
A rounding algorithm for approximating minimum Manhattan networks