Publications

Publications HAL du projet ANR. 17-CE22-0016

2023

Journal articles

auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
Finding the k Shortest Simple Paths: Time and Space trade-offs
article
ACM Journal of Experimental Algorithmics, 2023, 28, pp.23. ⟨10.1145/3626567⟩
DOI
DOI : 10.1145/3626567
Accès au texte intégral et bibtex
https://hal.science/hal-03196830/file/JEA-HAL.pdf BibTex
auteur
Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle
titre
Treelength of series–parallel graphs
article
Discrete Applied Mathematics, 2023, 341, pp.16-30. ⟨10.1016/j.dam.2023.07.022⟩
DOI
DOI : 10.1016/j.dam.2023.07.022
Accès au texte intégral et bibtex
https://hal.science/hal-04268050/file/Series_parallel_graphs_of_treelength_2-4.pdf BibTex

Conference papers

auteur
Julien Bensmail, Victor Campos, Ana Karolinna Maia, Nicolas Nisse, Ana Silva
titre
Deciding the Erdős-Pósa property in 3-connected digraphs
article
WG 2023 – 49th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2023, Fribourg (CH), Switzerland
Accès au texte intégral et bibtex
https://inria.hal.science/hal-04084227/file/Directed_Cylindrical_Grid_and_Models___New_version-6.pdf BibTex
auteur
Jean-Claude Bermond, Michel Cosnard, David Coudert, Frédéric Havet
titre
Groupage sur le chemin pour borner la largeur de coupe
article
AlgoTel 2023 – 25èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2023, Cargese, France. pp.4
Accès au texte intégral et bibtex
https://inria.hal.science/hal-04076999/file/cutwidth-Algotel.pdf BibTex
auteur
Cinzia Di Giusto, Davide Ferré, Etienne Lozes, Nicolas Nisse
titre
Weakly Synchronous Systems with Three Machines Are Turing Powerful
article
RP 2023 – 17th International Conference on Reachability Problems, 2023, Nice, France. pp.28-41, ⟨10.1007/978-3-031-45286-4_3⟩
DOI
DOI : 10.1007/978-3-031-45286-4_3
Accès au texte intégral et bibtex
https://hal.science/hal-04273451/file/conference.pdf BibTex

Preprints, Working Papers, …

auteur
Alkida Balliu, Filippo Brunelli, Pierluigi Crescenzi, Dennis Olivetti, Laurent Viennot
titre
A Note on the Complexity of Maximizing Temporal Reachability via Edge Temporalisation of Directed Graphs
article
2023
Accès au texte intégral et bibtex
https://inria.hal.science/hal-04054527/file/main.pdf BibTex
auteur
Filippo Brunelli, Laurent Viennot
titre
Minimum-Cost Temporal Walks under Waiting-Time Constraints in Linear Time
article
2023
Accès au texte intégral et bibtex
https://inria.hal.science/hal-03864725/file/main-long.pdf BibTex

2022

Journal articles

auteur
Filippo Brunelli, Pierluigi Crescenzi, Laurent Viennot
titre
On The Complexity of Maximizing Temporal Reachability via Trip Temporalisation
article
Networks, 2022, pp.27. ⟨10.1002/net.22123⟩
DOI
DOI : 10.1002/net.22123
Accès au texte intégral et bibtex
https://inria.hal.science/hal-03430099/file/main.pdf BibTex
auteur
David Coudert, André Nusser, Laurent Viennot
titre
Enumeration of far-apart pairs by decreasing distance for faster hyperbolicity computation
article
ACM Journal of Experimental Algorithmics, 2022, 27 (1.15), pp.29. ⟨10.1145/3569169⟩
DOI
DOI : 10.1145/3569169
Accès au texte intégral et bibtex
https://inria.hal.science/hal-03837023/file/CNV-JEA.pdf BibTex
auteur
Guillaume Ducoffe, Michel Habib, Laurent Viennot
titre
Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) VC-dimension
article
SIAM Journal on Computing, 2022, 51 (5), pp.1506-1534. ⟨10.1137/20M136551X⟩
DOI
DOI : 10.1137/20M136551X
Accès au texte intégral et bibtex
https://hal.science/hal-03841015/file/vc-diameter.pdf BibTex

Conference papers

auteur
Ali Al-Zoobi, David Coudert, Arthur Finkelstein, Jean-Charles Régin
titre
On Finding k Earliest Arrival Time Journeys in Public Transit Networks
article
ICORES 2022 – 11th International Conference on Operations Research and Enterprise Systems, Feb 2022, Virtual event, France. pp.314-325, ⟨10.5220/0010977200003117⟩
DOI
DOI : 10.5220/0010977200003117
Accès au texte intégral et bibtex
https://inria.hal.science/hal-03559992/file/ptkssp.pdf BibTex
auteur
David Coudert, André Nusser, Laurent Viennot
titre
Hyperbolicity Computation through Dominating Sets
article
ALENEX 2022 – SIAM Symposium on Algorithm Engineering and Experiments, Jan 2022, Alexandria, VA, United States. pp.78-90, ⟨10.1137/1.9781611977042.7⟩
DOI
DOI : 10.1137/1.9781611977042.7
Accès au texte intégral et bibtex
https://inria.hal.science/hal-03431155/file/domset-main-arxiv.pdf BibTex
auteur
David Coudert, André Nusser, Laurent Viennot
titre
Dominer pour calculer l’hyperbolicité des graphes
article
AlgoTel 2022 – 24èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2022, Saint-Rémy-Lès-Chevreuse, France
Accès au texte intégral et bibtex
https://hal.science/hal-03648264/file/algotel2022final.pdf BibTex

2021

Journal articles

auteur
Filippo Brunelli, Pierluigi Crescenzi, Laurent Viennot
titre
On Computing Pareto Optimal Paths in Weighted Time-Dependent Networks
article
Information Processing Letters, In press, ⟨10.1016/j.ipl.2020.106086⟩
DOI
DOI : 10.1016/j.ipl.2020.106086
Accès au texte intégral et bibtex
https://inria.hal.science/hal-03095828/file/main.pdf BibTex
auteur
Guillaume Ducoffe, Michel Habib, Laurent Viennot
titre
Fast Diameter Computation within Split Graphs
article
Discrete Mathematics and Theoretical Computer Science, 2021, ⟨10.46298/dmtcs.6422⟩
DOI
DOI : 10.46298/dmtcs.6422
Accès au texte intégral et bibtex
https://inria.hal.science/hal-02307397/file/DHV-dmtcs.pdf BibTex

Conference papers

auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
De la difficulté de trouver des chemins dissimilaires
article
ALGOTEL 2021 – 23èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Sep 2021, La Rochelle, France
Accès au texte intégral et bibtex
https://hal.science/hal-03219987/file/On_the_k_top_shortest_paths_with_diversity_constraints_c.pdf BibTex
auteur
Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle
titre
Treelength of Series-parallel graphs
article
LAGOS 2021 – XI Latin and American Algorithms, Graphs and Optimization Symposium, May 2021, São Paulo / Virtual, Brazil. ⟨10.1016/j.procs.2021.11.008⟩
DOI
DOI : 10.1016/j.procs.2021.11.008
Accès au texte intégral et bibtex
https://inria.hal.science/hal-03175837/file/Lagos_2021%289%29.pdf BibTex

Book sections

auteur
Nicolas Isoart, Jean-Charles Régin
titre
A k-opt based constraint for the TSP
article
the 27th International Conference on Principles and Practice of Constraint Programming, In press
Accès au bibtex
BibTex
auteur
Nicolas Isoart, Jean-Charles Régin
titre
A linear time algorithm for the k-cutset constraint
article
the 27th International Conference on Principles and Practice of Constraint Programming, In press
Accès au bibtex
BibTex

Reports

auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
On the complexity of finding $k$ shortest dissimilar paths in a graph
article
[Research Report] Inria; CNRS; I3S; Université Côte d’Azur. 2021, pp.9
Accès au texte intégral et bibtex
https://hal.science/hal-03187276/file/On_the_k_top_shortest_paths_with_dissimilarity_constraints-v2.pdf BibTex
auteur
David Coudert, Ali Al Zoobi, Arthur Finkelstein
titre
On finding $k$ earliest arrival time journeys in public transit networks
article
[Research Report] Inria. 2021
Accès au texte intégral et bibtex
https://hal.science/hal-03264788/file/Multimod_kssp_Hal.pdf BibTex

Software

auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
k shortest simple paths
article
2021, ⟨swh:1:dir:4dc5b3b01ddcd9091dd5a628916638a1cefd8e0c;origin=https://gitlab.inria.fr/dcoudert/k-shortest-simple-paths/;visit=swh:1:snp:f0cc7e5f3ec6200d39061db55146a7ab340fee95;anchor=swh:1:rev:124c172d617e485a6b3cd5dc6db7768d86a3a5af⟩
Accès au bibtex
BibTex
auteur
David Coudert, André Nusser, Laurent Viennot
titre
Hyperbolicity
article
2021, ⟨swh:1:dir:719d653945a6c7958028c8b5aab00960fb52d551;origin=https://gitlab.inria.fr/dcoudert/hyperbolicity/;visit=swh:1:snp:0d13e52e2c1d0b4e50153af070155c216f148d3e;anchor=swh:1:rev:4f9c8ce6eed890ed5bad1f56ff550577b4819bad⟩
Accès au bibtex
BibTex

2020

Conference papers

auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
Compromis espace-temps pour le problème de k plus courts chemins simples
article
ALGOTEL 2020 – 22èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Sep 2020, Lyon, France. pp.4
Accès au texte intégral et bibtex
https://inria.hal.science/hal-02835953/file/algotel-FinalVersion.pdf BibTex
auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
Space and Time Trade-Off for the k Shortest Simple Paths Problem
article
SEA 2020 – 18th International Symposium on Experimental Algorithms, Jun 2020, Catania, Italy. pp.13, ⟨10.4230/LIPIcs.SEA.2020.18⟩
DOI
DOI : 10.4230/LIPIcs.SEA.2020.18
Accès au texte intégral et bibtex
https://inria.hal.science/hal-02865918/file/LIPIcs-SEA-2020-18.pdf BibTex
auteur
Guillaume Ducoffe, Michel Habib, Laurent Viennot
titre
Diameter computation on H-minor free graphs and graphs of bounded (distance) VC-dimension
article
SODA 2020 – ACM-SIAM Symposium on Discrete Algorithms, Jan 2020, Salt Lake City, United States
Accès au texte intégral et bibtex
https://inria.hal.science/hal-02340382/file/vc-diameter.pdf BibTex

Book sections

auteur
Nicolas Isoart, Jean-Charles Régin
titre
Parallelization of TSP Solving in CP
article
International Conference on Principles and Practice of Constraint Programming, pp.410-426, 2020, ⟨10.1007/978-3-030-58475-7_24⟩
DOI
DOI : 10.1007/978-3-030-58475-7_24
Accès au bibtex
BibTex

Reports

auteur
Ali Al Zoobi, David Coudert, Nicolas Nisse
titre
Space and time trade-off for the k shortest simple paths problem
article
[Research Report] Inria & Université Cote d’Azur, CNRS, I3S, Sophia Antipolis, France. 2020
Accès au texte intégral et bibtex
https://hal.science/hal-02465317/file/HAL_kSSP.pdf BibTex
auteur
Thomas Dissaux, Guillaume Ducoffe, Nicolas Nisse, Simon Nivelle
titre
Treelength of Series-parallel graphs
article
[Research Report] Inria & Université Cote d’Azur, CNRS, I3S, Sophia Antipolis, France. 2020
Accès au texte intégral et bibtex
https://hal.science/hal-03010346/file/Lagos_2021.pdf BibTex

Preprints, Working Papers, …

auteur
Samvel Balassanian Dersarkissian, Arnaud Malapert
titre
Flexibilité et Portabilité pour Embarrassingly Parallel Search
article
2020
Accès au texte intégral et bibtex
https://hal.science/hal-02494158/file/preprint_draft_10971-1.pdf BibTex

2019

Conference papers

auteur
Guillaume Ducoffe, Michel Habib, Laurent Viennot
titre
Fast Diameter Computation within Split Graphs
article
COCOA 2019 – 13th Annual International Conference on Combinatorial Optimization and Applications, Dec 2019, Xiamen, China
Accès au bibtex
https://arxiv.org/pdf/1910.03438 BibTex
auteur
Nicolas Isoart, Jean-Charles Régin
titre
Introduction de contraintes structurelles pour la résolution du problème du voyageur de commerce
article
JFPC, Jun 2019, Albi, France
Accès au texte intégral et bibtex
https://hal.science/hal-02160046/file/jfpc.pdf BibTex
auteur
Adrian Kosowski, Przemysław Uznański, Laurent Viennot
titre
Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling
article
PODC ’19 – ACM Symposium on Principles of Distributed Computing, Jul 2019, Toronto, Canada. pp.272-279, ⟨10.1145/3293611.3331625⟩
DOI
DOI : 10.1145/3293611.3331625
Accès au bibtex
https://arxiv.org/pdf/1902.07055 BibTex
auteur
Duc-Minh Phan, Laurent Viennot
titre
Fast Public Transit Routing with Unrestricted Walking through Hub Labeling
article
Special Event on Analysis of Experimental Algorithms (SEA2), Jun 2019, Kalamata, Greece
Accès au texte intégral et bibtex
https://inria.hal.science/hal-02161283/file/arxiv.pdf BibTex

Reports

auteur
Nicolas Isoart, Jean-Charles Régin
titre
An adaptive CP method for TSP solving
article
[Research Report] Université Côte d’Azur. 2019
Accès au texte intégral et bibtex
https://hal.science/hal-02165374/file/LagrangianFilter.pdf BibTex

Comments are closed.