Search

Your search keyword '"Coudert, David"' showing total 362 results
Start Over Author "Coudert, David"

Refine your results

more »

more »

more »

more »
362 results on '"Coudert, David"'

1. Practical Computation of Graph VC-Dimension

Author

Coudert, David, Csikós, Mónika, Ducoffe, Guillaume, and Viennot, Laurent

Subjects
Computer Science - Data Structures and Algorithms
Abstract

For any set system $H=(V,R), \ R \subseteq 2^V$, a subset $S \subseteq V$ is called \emph{shattered} if every $S' \subseteq S$ results from the intersection of $S$ with some set in $\R$. The \emph{VC-dimension} of $H$ is the size of a largest shattered set in $V$. In this paper, we focus on the problem of computing the VC-dimension of graphs. In particular, given a graph $G=(V,E)$, the VC-dimension of $G$ is defined as the VC-dimension of $(V, \mathcal N)$, where $\mathcal N$ contains each subset of $V$ that can be obtained as the closed neighborhood of some vertex $v \in V$ in $G$. Our main contribution is an algorithm for computing the VC-dimension of any graph, whose effectiveness is shown through experiments on various types of practical graphs, including graphs with millions of vertices. A key aspect of its efficiency resides in the fact that practical graphs have small VC-dimension, up to 8 in our experiments. As a side-product, we present several new bounds relating the graph VC-dimension to other classical graph theoretical notions. We also establish the $W[1]$-hardness of the graph VC-dimension problem by extending a previous result for arbitrary set systems.

Published
2024

2. Hyperbolicity Computation through Dominating Sets

Author

Coudert, David, Nusser, André, and Viennot, Laurent

Subjects
Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms, Computer Science - Networking and Internet Architecture
Abstract

Hyperbolicity is a graph parameter related to how much a graph resembles a tree with respect to distances. Its computation is challenging as the main approaches consist in scanning all quadruples of the graph or using fast matrix multiplication as building block, both are not practical for large graphs. In this paper, we propose and evaluate an approach that uses a hierarchy of distance-k dominating sets to reduce the search space. This technique, compared to the previous best practical algorithms, enables us to compute the hyperbolicity of graphs with unprecedented size (up to a million nodes) and speeds up the computation of previously attainable graphs by up to 3 orders of magnitude while reducing the memory consumption by up to more than a factor of 23.

Published
2021

3. Enumeration of Far-Apart Pairs by Decreasing Distance for Faster Hyperbolicity Computation

Author

Coudert, David, Nusser, André, and Viennot, Laurent

Subjects
Computer Science - Data Structures and Algorithms
Abstract

Hyperbolicity is a graph parameter which indicates how much the shortest-path distance metric of a graph deviates from a tree metric. It is used in various fields such as networking, security, and bioinformatics for the classification of complex networks, the design of routing schemes, and the analysis of graph algorithms. Despite recent progress, computing the hyperbolicity of a graph remains challenging. Indeed, the best known algorithm has time complexity $O(n^{3.69})$, which is prohibitive for large graphs, and the most efficient algorithms in practice have space complexity $O(n^2)$. Thus, time as well as space are bottlenecks for computing hyperbolicity. In this paper, we design a tool for enumerating all far-apart pairs of a graph by decreasing distances. A node pair $(u, v)$ of a graph is far-apart if both $v$ is a leaf of all shortest-path trees rooted at $u$ and $u$ is a leaf of all shortest-path trees rooted at $v$. This notion was previously used to drastically reduce the computation time for hyperbolicity in practice. However, it required the computation of the distance matrix to sort all pairs of nodes by decreasing distance, which requires an infeasible amount of memory already for medium-sized graphs. We present a new data structure that avoids this memory bottleneck in practice and for the first time enables computing the hyperbolicity of several large graphs that were far out-of-reach using previous algorithms. For some instances, we reduce the memory consumption by at least two orders of magnitude. Furthermore, we show that for many graphs, only a very small fraction of far-apart pairs have to be considered for the hyperbolicity computation, explaining this drastic reduction of memory. As iterating over far-apart pairs in decreasing order without storing them explicitly is a very general tool, we believe that our approach might also be relevant to other problems.

Published
2021

4. Fully polynomial FPT algorithms for some classes of bounded clique-width graphs

Author

Coudert, David, Ducoffe, Guillaume, and Popa, Alexandru

Subjects
Computer Science - Data Structures and Algorithms, Computer Science - Computational Complexity, Computer Science - Discrete Mathematics, Mathematics - Combinatorics
Abstract

Parameterized complexity theory has enabled a refined classification of the difficulty of NP-hard optimization problems on graphs with respect to key structural properties, and so to a better understanding of their true difficulties. More recently, hardness results for problems in P were achieved using reasonable complexity theoretic assumptions such as: Strong Exponential Time Hypothesis (SETH), 3SUM and All-Pairs Shortest-Paths (APSP). According to these assumptions, many graph theoretic problems do not admit truly subquadratic algorithms, nor even truly subcubic algorithms (Williams and Williams, FOCS 2010 and Abboud, Grandoni, Williams, SODA 2015). A central technique used to tackle the difficulty of the above mentioned problems is fixed-parameter algorithms for polynomial-time problems with polynomial dependency in the fixed parameter (P-FPT). This technique was introduced by Abboud, Williams and Wang in SODA 2016 and continued by Husfeldt (IPEC 2016) and Fomin et al. (SODA 2017), using the treewidth as a parameter. Applying this technique to clique-width, another important graph parameter, remained to be done. In this paper we study several graph theoretic problems for which hardness results exist such as cycle problems (triangle detection, triangle counting, girth, diameter), distance problems (diameter, eccentricities, Gromov hyperbolicity, betweenness centrality) and maximum matching. We provide hardness results and fully polynomial FPT algorithms, using clique-width and some of its upper-bounds as parameters (split-width, modular-width and $P\_4$-sparseness). We believe that our most important result is an ${\cal O}(k^4 \cdot n + m)$-time algorithm for computing a maximum matching where $k$ is either the modular-width or the $P\_4$-sparseness. The latter generalizes many algorithms that have been introduced so far for specific subclasses such as cographs, $P\_4$-lite graphs, $P\_4$-extendible graphs and $P\_4$-tidy graphs. Our algorithms are based on preprocessing methods using modular decomposition, split decomposition and primeval decomposition. Thus they can also be generalized to some graph classes with unbounded clique-width.

Published
2017

6. Feasibility study on distributed simulations of BGP

Author

Coudert, David, Hogie, Luc, Lancin, Aurélien, Papadimitriou, Dimitri, Pérennes, Stéphane, and Tahiri, Issam

Subjects
Computer Science - Networking and Internet Architecture
Abstract

The Autonomous System (AS)-level topology of the Internet that currently comprises 40k ASs, is growing at a rate of about 10% per year. In these conditions, Border Gateway Protocol (BGP), the inter-domain routing protocol of the Internet starts to show its limits, among others in terms of the number of routing table entries it can dynamically process and control. To overcome this challenging situation, the design but also the evaluation of alternative dynamic routing models and their comparison with BGP shall be performed by means of simulation. For this purpose, DRMSim, a Dynamic Routing Model Simulator, was developed that provides the means for large-scale simulations of various routing models including BGP. By means of this discrete-event simulator, execution of path-vector routing, e.g. BGP, and other compact routing models have been successfully performed on network topologies comprising more than ten thousand (abstract) nodes. However, to simulate dynamic routing schemes like BGP, DRMSim needs enhancements to support current Internet size (40k ASs) and even more by considering its evolution (up to 100k ASs). This paper proposes a feasibility study of the extension of DRMSim so as to support the Distributed Parallel Discrete Event paradigm. We first detail the possible distribution models and their associated communication overhead. Then, we analyze the communication overhead of such a distributed simulator by executing BGP on a partitioned topology according to different scenarios. Finally, we conclude on the feasibility of such a simulator by computing the expected additional time required by a distributed simulation of BGP compared to its sequential simulation.

Published
2013

7. Feasibility study on distributed simulations of BGP

Author

Coudert, David, Hogie, Luc, Lancin, Aurélien, Papadimitriou, Dimitri, Pérennes, Stéphane, and Tahiri, Issam

Subjects
Computer Science - Networking and Internet Architecture
Abstract

The Autonomous System (AS) topology of the Internet (up to 61k ASs) is growing at a rate of about 10% per year. The Border Gateway Protocol (BGP) starts to show its limits in terms of the number of routing table entries it can dynamically process and control. Due to the increasing routing information processing and storage, the same trend is observed for routing model simulators such as DRMSim specialized in large-scale simulations of routing models. Therefore, DRMSim needs enhancements to support the current size of the Internet topology and its evolution (up to 100k ASs). To this end, this paper proposes a feasibility study of the extension of DRMSim so as to support the Distributed Parallel Discrete Event paradigm. We first detail the possible distribution models and their associated communication overhead. Then, we analyze this overhead by executing BGP on a partitioned topology according to different scenarios. Finally, we conclude on the feasibility of such a simulator by computing the expected additional time required by a distributed simulation of BGP compared to its sequential simulation., Comment: 26th ACM/IEEE/SCS Workshop on Principles of Advanced and Distributed Simulation (2012)

Published
2012

8. A distributed algorithm for computing and updating the process number of a forest

Author

Coudert, David, Huc, Florian, and Mazauric, Dorian

Subjects
Computer Science - Discrete Mathematics
Abstract

In this paper, we present a distributed algorithm to compute various parameters of a tree such as the process number, the edge search number or the node search number and so the pathwidth. This algorithm requires n steps, an overall computation time of O(n log(n)), and n messages of size log_3(n)+3. We then propose a distributed algorithm to update the process number (or the node search number, or the edge search number) of each component of a forest after adding or deleting an edge. This second algorithm requires O(D) steps, an overall computation time of O(D log(n)), and O(D) messages of size log_3(n)+3, where D is the diameter of the modified connected component. Finally, we show how to extend our algorithms to trees and forests of unknown size using messages of less than 2a+4+e bits, where a is the parameter to be determined and e=1 for updates algorithms.

Published
2008

10. Bin Packing with Colocations

Author

Bermond, Jean-Claude, Cohen, Nathann, Coudert, David, Letsios, Dimitrios, Milis, Ioannis, Pérennes, Stéphane, Zissimopoulos, Vassilis, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Jansen, Klaus, editor, and Mastrolilli, Monaldo, editor

Published
2017
Full Text
View/download PDF

13. Leanness Computation: Small Values and Special Graph Classes.

Author

Coudert, David, Coulomb, Samuel, and Ducoffe, Guillaume

Subjects
*GEOMETRIC vertices, *GRAPH algorithms, *MATHEMATICAL bounds, *COMPUTATIONAL complexity, *MATHEMATICAL formulas
Abstract

Let u and v be vertices in a connected graph G = (V, E). For any integer k such that 0 ≤ k ≤ dG(u, v), the k-slice Sk(u, v) contains all vertices x on a shortest uv-path such that dG(u, x) = k. The leanness of G is the maximum diameter of a slice. This metric graph invariant has been studied under different names, such as,,interval thinness” and,,fellow traveler property”. Graphs with leanness equal to 0, a.k.a. geodetic graphs, also have received special attention in Graph Theory. The practical computation of leanness in real-life complex networks has been studied recently (Mohammed et al., COMPLEX NETWORKS’21). In this paper, we give a finer-grained complexity analysis of two related problems, namely: deciding whether the leanness of a graph G is at most some small value ℓ; and computing the leanness on specific graph classes. We obtain improved algorithms in some cases, and time complexity lower bounds under plausible hypotheses. [ABSTRACT FROM AUTHOR]

Published
2024

15. Groupage sur le chemin pour borner la largeur de coupe

Author

Bermond, Jean-Claude, Cosnard, Michel, Coudert, David, Havet, Frédéric, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), and ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015)

Subjects
densité, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], cutwidth, groupage, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], largeur de coupe, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Abstract

International audience; La largeur de coupe (cutwidth) est un paramètre utilisé dans de nombreux problèmes d'ordonnancement linéaire (layout). Calculer la largeur de coupe est un problème NP-complet, mais il est possible de concevoir des algorithmes de branch-and-bound efficaces si on dispose de bonnes bornes inférieures pour couper des branches lors de l'exploration. Savoir évaluer rapidement de bonnes bornes dans chaque noeud de l'arbre de recherche est donc crucial. Dans cet article, nous donnons de nouvelles bornes basées sur différents paramètres de densité du graphe. Nous donnons aussi une borne inférieure basée sur le groupage de requêtes sur le chemin.

Published
2023

16. On Computing the Hyperbolicity of Real-World Graphs

Author

Borassi, Michele, Coudert, David, Crescenzi, Pierluigi, Marino, Andrea, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Bansal, Nikhil, editor, and Finocchi, Irene, editor

Published
2015
Full Text
View/download PDF

21. Experimental Evaluation of a Branch and Bound Algorithm for Computing Pathwidth

Author

Coudert, David, Mazauric, Dorian, Nisse, Nicolas, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Kobsa, Alfred, editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Weikum, Gerhard, editor, Gudmundsson, Joachim, editor, and Katajainen, Jyrki, editor

Published
2014
Full Text
View/download PDF

22. Connectivity Inference in Mass Spectrometry Based Structure Determination

Author

Agarwal, Deepesh, Araujo, Julio-Cesar Silva, Caillouet, Christelle, Cazals, Frederic, Coudert, David, Pérennes, Stephane, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Bodlaender, Hans L., editor, and Italiano, Giuseppe F., editor

Published
2013
Full Text
View/download PDF

23. Dominer pour calculer l'hyperbolicité des graphes

Author

Coudert, David, Nusser, André, Viennot, Laurent, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Basic Algorithms Research Copenhagen (BARC), University of Copenhagen = Københavns Universitet (UCPH), Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), Inria Paris-Rocquencourt, Institut National de Recherche en Informatique et en Automatique (Inria), VILLUM Foundation grant 16582, ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), Coudert, David, Idex UCA JEDI - - UCA JEDI2015 - ANR-15-IDEX-0001 - IDEX - VALID, Routage dans les grands réseaux de transports multi-modal - - MultiMod2017 - ANR-17-CE22-0016 - AAPG2017 - VALID, and Théorie métrique des graphes - - DISTANCIA2017 - ANR-17-CE40-0015 - AAPG2017 - VALID

Subjects
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], hyperbolicité, [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], Algorithmes de graphes, ingénierie algorithmique, domination
Abstract

International audience; L'hyperbolicité est un paramètre de graphe mesurant l'écart entre la métrique des distances dans le graphe et celle d'un arbre. Cette propriété peut se calculer en temps $O(n^4)$ et en espace $O(n^2)$. En effet, les principales approches consistent à considérer tous les quadruplets du graphe, ou bien se basent sur des produits de matrices, et ne passent pas à l'échelle. Dans cet article, nous proposons et évaluons une approche qui utilise une hiérarchie d'ensembles dominants à distance $k$ pour réduire l'espace de recherche. Cette technique, comparée aux meilleurs algorithmes pratiques existants, nous permet de calculer l'hyperbolicité de graphes d'une taille sans précédent, jusqu'à un million de sommets.

Published
2022

24. Energy Saving in Fixed Wireless Broadband Networks

Author

Coudert, David, Nepomuceno, Napoleão, Tahiri, Issam, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Pahl, Julia, editor, Reiners, Torsten, editor, and Voß, Stefan, editor

Published
2011
Full Text
View/download PDF

25. A Chance-Constrained Model and Cutting Planes for Fixed Broadband Wireless Networks

Author

Claßen, Grit, Coudert, David, Koster, Arie M. C. A., Nepomuceno, Napoleão, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Pahl, Julia, editor, Reiners, Torsten, editor, and Voß, Stefan, editor

Published
2011
Full Text
View/download PDF

28. Tradeoffs in Process Strategy Games with Application in the WDM Reconfiguration Problem

Author

Cohen, Nathann, Coudert, David, Mazauric, Dorian, Nepomuceno, Napoleão, Nisse, Nicolas, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Boldi, Paolo, editor, and Gargano, Luisa, editor

Published
2010
Full Text
View/download PDF

29. Designing Hypergraph Layouts to GMPLS Routing Strategies

Author

Bermond, Jean-Claude, Coudert, David, Moulierac, Joanna, Pérennes, Stéphane, Sau, Ignasi, Solano Donado, Fernando, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Kutten, Shay, editor, and Žerovnik, Janez, editor

Published
2010
Full Text
View/download PDF

30. Edge-Simple Circuits through 10 Ordered Vertices in Square Grids

Author

Coudert, David, Giroire, Frédéric, Sau, Ignasi, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Fiala, Jiří, editor, Kratochvíl, Jan, editor, and Miller, Mirka, editor

Published
2009
Full Text
View/download PDF

31. MPLS Label Stacking on the Line Network

Author

Bermond, Jean-Claude, Coudert, David, Moulierac, Joanna, Perennes, Stéphane, Rivano, Hervé, Sau, Ignasi, Solano Donado, Fernando, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Fratta, Luigi, editor, Schulzrinne, Henning, editor, Takahashi, Yutaka, editor, and Spaniol, Otto, editor

Published
2009
Full Text
View/download PDF

33. Computing and Updating the Process Number in Trees

Author

Coudert, David, Huc, Florian, Mazauric, Dorian, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Baker, Theodore P., editor, Bui, Alain, editor, and Tixeuil, Sébastien, editor

Published
2008
Full Text
View/download PDF

34. Traffic Grooming on the Path

Author

Bermond, Jean-Claude, Braud, Laurent, Coudert, David, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Pelc, Andrzej, editor, and Raynal, Michel, editor

Published
2005
Full Text
View/download PDF

36. Bin Packing with Colocations

Author

Bermond, Jean-Claude, primary, Cohen, Nathann, additional, Coudert, David, additional, Letsios, Dimitrios, additional, Milis, Ioannis, additional, Pérennes, Stéphane, additional, and Zissimopoulos, Vassilis, additional

Published
2017
Full Text
View/download PDF

38. OTIS-Based multi-hop multi-OPS lightwave networks

Author

Coudert, David, Ferreira, Afonso, Muñoz, Xavier, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Rolim, José, editor, Mueller, Frank, editor, Zomaya, Albert Y., editor, Ercal, Fikret, editor, Olariu, Stephan, editor, Ravindran, Binoy, editor, Gustafsson, Jan, editor, Takada, Hiroaki, editor, Olsson, Ron, editor, Kale, Laxmikant V., editor, Beckman, Pete, editor, Haines, Matthew, editor, ElGindy, Hossam, editor, Caromel, Denis, editor, Chaumette, Serge, editor, Fox, Geoffrey, editor, Pan, Yi, editor, Li, Keqin, editor, Yang, Tao, editor, Chiola, G., editor, Conte, G., editor, Mancini, L. V., editor, Méry, Domenique, editor, Sanders, Beverly, editor, Bhatt, Devesh, editor, and Prasanna, Viktor, editor

Published
1999
Full Text
View/download PDF

41. Hyperbolicity Computation through Dominating Sets

Author

Coudert, David, Nusser, André, Viennot, Laurent, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Max Planck Institute for Informatics [Saarbrücken], Institut de Recherche en Informatique Fondamentale (IRIF (UMR_8243)), Centre National de la Recherche Scientifique (CNRS)-Université de Paris (UP), Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), ANR-17-CE40-0015,DISTANCIA,Théorie métrique des graphes(2017), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Centre National de la Recherche Scientifique (CNRS)-Université Paris Cité (UPCité), and COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)

Subjects
Networking and Internet Architecture (cs.NI), FOS: Computer and information sciences, graph algorithms, Discrete Mathematics (cs.DM), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Computer Science - Networking and Internet Architecture, ACM: G.: Mathematics of Computing/G.2: DISCRETE MATHEMATICS/G.2.2: Graph Theory, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Gromov hyperbolicity, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), algorithm engineering, Computer Science - Discrete Mathematics
Abstract

International audience; Hyperbolicity is a graph parameter related to how much a graph resembles a tree with respect to distances. Its computation is challenging as the main approaches consist in scanning all quadruples of the graph or using fast matrix multiplication as building block, both are not practical for large graphs. In this paper, we propose and evaluate an approach that uses a hierarchy of distance-k dominating sets to reduce the search space. This technique, compared to the previous best practical algorithms, enables us to compute the hyperbolicity of graphs with unprecedented size (up to a million nodes) and speeds up the computation of previously attainable graphs by up to 3 orders of magnitude while reducing the memory consumption by up to more than a factor of 23.

Published
2022
Full Text
View/download PDF

42. On Finding k Earliest Arrival Time Journeys in Public Transit Networks

Author

Al-Zoobi, Ali, Coudert, David, Finkelstein, Arthur, Régin, Jean-Charles, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), Instant System, Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe CEP, Modèles Discrets pour les Systèmes Complexes (Laboratoire I3S - MDSC), ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), and ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017)

Subjects
shortest path, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], dissimilar paths, [INFO]Computer Science [cs], [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Public Transit Routing
Abstract

International audience; Journey planning in (schedule-based) public transit networks has attracted interest from researchers in the last decade. In particular, many algorithms aiming at efficiently answering queries of journey planning have been proposed. However, most of the proposed methods give the user a single or a limited number of journeys in practice, which is undesirable in a transportation context. In this paper, we consider the problem of finding k earliest arrival time journeys in public transit networks from a given origin to a given destination, i.e., an earliest arrival journey from the origin to the destination, a second earliest arrival journey, etc. until the k th earliest arrival journey. For this purpose, we propose an algorithm, denoted by Yen-Public Transit (Y-PT), which extends to public transit networks the algorithm proposed by Yen to find the top-k shortest simple paths in a graph. Moreover, we propose a more refined algorithm, called Postponed Yen-Public Transit (PY-PT), enabling a considerable speed up in practice. Our experiments on several public transit networks show that, in practice, PY-PT is faster than Y-PT by an order of magnitude.

Published
2022
Full Text
View/download PDF

43. Optimizing FANET deployment for mobile sensor tracking in disaster management scenario

Author

Dias Da Silva, Igor, Caillouet, Christelle, Coudert, David, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)

Subjects
[INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], column generation, disaster management, ComputerSystemsOrganization_SPECIAL-PURPOSEANDAPPLICATION-BASEDSYSTEMS, ComputerApplications_COMPUTERSINOTHERSYSTEMS, linear programming, UAVs, ComputingMethodologies_ARTIFICIALINTELLIGENCE
Abstract

International audience; This paper addresses the data collection problem using the minimum number of unmanned aerial vehicles (UAVs) in a disaster management scenario where mobile sensors are investigating the devastated area. Critical information needs to be quickly gathered for processing by the rescue team, so the use of UAVs in this situation is of great interest. We propose an optimal model for computing the trajectories of the UAVs while guaranteeing the total coverage of the ground mobile sensors and connectivity among the UAVs with a central base station dedicated to data processing. Our model is based on a decomposition model and is solved effectively using column generation. We show that we can provide a plan for deploying the UAVs minimizing the total traveled distance.

Published
2021
Full Text
View/download PDF

45. De la difficulté de trouver des chemins dissimilaires

Author

Al Zoobi, Ali, Coudert, David, Nisse, Nicolas, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), This work has been supported by the UCAJEDI Investments in the Future project managed by the National Research Agency (ANR-15-IDEX-01), project MULTIMOD (ANR-17-CE22-0016), project Digraphs (ANR-19-CE48-0013), and by Region Sud PACA., ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015 - 2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), and Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)

Subjects
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC], $k$ plus courts chemins simples, Similarité entre chemins
Abstract

International audience; Lorsque l'on demande à son GPS un chemin pour aller à La Rochelle, celui-ci propose généralement plusieurs chemins assez différents les uns des autres : l'un par l'autoroute, l'autre par la côte, un pas cher, etc. La notion de (dis)similarité entre deux chemins a été définie, dans la littérature, de différentes manières qui toutes sont liées à un ratio entre la longueur de leur intersection et une certaine fonction de leurs longueurs. Nous étudions la complexité de plusieurs variantes du problème du calcul de chemins "dissimilaires" (dont la mesure de similarité n'excède pas un certain seuil) entre deux sommets d'un graphe orienté et pondéré. Pour quatre des mesures les plus étudiées dans la littérature, nous donnons une preuve unifiée et simple du fait que trouver $k$ plus courts chemins dissimilaires est NP-complet. En pratique, ce que l'on cherche est une alternative à un ou des chemins que l'on connait a priori. Nos résultats principaux concernent ce type de problème. Plus précisément, pour chacune des quatre mesures considérées, nous montrons que si $k\geq 2 $chemins sont donnés, en trouver un nouveau qui soit dissimilaire des premiers est NP-complet. Enfin, nous montrons que si un chemin $P$ est donné, trouver un plus court chemin parmi ceux qui sont dissimilaires de $P$ est NP-complet. Ce dernier résultat est à mettre en contraste avec le fait que, pour l'une des mesures, trouver un chemin dissimilaire à un chemin donné peut être résolu très simplement en temps polynomial.

Published
2021

47. On finding $k$ earliest arrival time journeys in public transit networks

Author

Coudert, David, Al Zoobi, Ali, Finkelstein, Arthur, Combinatorics, Optimization and Algorithms for Telecommunications (COATI), COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (... - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Instant System, This work has been supported by the French government, through the UCAjedi Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-15-IDEX-01, the ANR project MULTIMOD with the reference number ANR-17-CE22-0016, the ANR project Digraphs with the reference number ANR-19-CE48-0013, and by Région Sud PACA., Inria, ANR-15-IDEX-0001,UCA JEDI,Idex UCA JEDI(2015), ANR-17-CE22-0016,MultiMod,Routage dans les grands réseaux de transports multi-modal(2017), ANR-19-CE48-0013,DIGRAPHS,Digraphes(2019), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Université Nice Sophia Antipolis (1965 - 2019) (UNS), COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS), and COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-COMUE Université Côte d'Azur (2015-2019) (COMUE UCA)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UCA)

Subjects
shortest path, routing, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], timetables, [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO], Journey planning
Abstract

Journey planning in (schedule-based) public transit networks has attracted interest from researchers in the last decade. In particular, many algorithms aiming at efficiently answering queries of journey planning have been proposed. However, most of the proposed methods give the user a single or a limited number of journeys in practice, which is undesirable in a transportation context. In this paper, we consider the problem of finding $k$ earliest arrival time journeys in public transit networks from a given origin to a given destination, i.e, an earliest arrival journey from the origin to the destination, a second earliest arrival journey, etc. until the $k^{th}$ earliest arrival journey. For this purpose, we propose an algorithm, denoted by Yen-Public Transit (Y-PT), that extends to public transit networks the algorithm proposed by Yen to find the top-$k$ shortest simple paths in a graph. Moreover, we propose a more refined algorithm, called Postponed Yen-Public Transit (PY-PT), enabling a considerable speed up in practice. Our experiments on several public transit networks show that, in practice, PY-PT is faster than Y-PT by an order of magnitude.

Published
2021

Catalog

Books, media, physical & digital resources
See catalog results