Maximum Weight Disjoint Paths in Outerplanar Graphs via Single-Tree Cut Approximators

Autor: F. Bruce Shepherd, Henry Xia, Guyslain Naves

Publikováno v: Integer Programming and Combinatorial Optimization
Integer Programming and Combinatorial Optimization, 12707, Springer International Publishing, pp.326-339, 2021, Lecture Notes in Computer Science, ⟨10.1007/978-3-030-73879-2_23⟩
Integer Programming and Combinatorial Optimization ISBN: 9783030738785
IPCO

Since 1997 there has been a steady stream of advances for the maximum disjoint paths problem. Achieving tractable results has usually required focusing on relaxations such as: (i) to allow some bounded edge congestion in solutions, (ii) to only consi

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::606fbee66ad10792d4de1f6ca8648cbe
https://hal.archives-ouvertes.fr/hal-03514641/file/USRA_2020.pdf

Packing and Covering with Balls on Busemann Surfaces

Autor: Guyslain Naves, Bertrand Estellon, Victor Chepoi

Publikováno v: Discrete and Computational Geometry
Discrete and Computational Geometry, 2017, 57, pp.985-1011. ⟨10.1007/s00454-017-9872-0⟩
HAL
Discrete and Computational Geometry, Springer Verlag, 2017, 57 (4), pp.985-1011. ⟨10.1007/s00454-017-9872-0⟩
Discrete and Computational Geometry, Springer Verlag, 2017, 57 (4), pp.985-1011. 〈10.1007/s00454-017-9872-0〉

In this note we prove that for any compact subset $S$ of a Busemann surface $({\mathcal S},d)$ (in particular, for any simple polygon with geodesic metric) and any positive number $\delta$, the minimum number of closed balls of radius $\delta$ with c

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0a202060310d41745fb30e3c4b38c88b
https://hal.science/hal-03581534

Balancing lists: a proof pearl

Autor: Arnaud Spiwack, Guyslain Naves

Publikováno v: Lecture Notes in Computer Science
5th International Conference, ITP 2014
5th International Conference, ITP 2014, Jul 2014, Vienna, Austria. pp.437-449, ⟨10.1007/978-3-319-08970-6_28⟩
Interactive Theorem Proving ISBN: 9783319089690
ITP

Starting with an algorithm to turn lists into full trees which uses non-obvious invariants and partial functions, we progressively encode the invariants in the types of the data, removing most of the burden of a correctness proof. The invariants are

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::51bac348ae55e5929df627ebe2697dc1

Approximating Rooted Steiner Network

Autor: Joseph Cheriyan, Bundit Laekhanukit, Guyslain NAVES, Adrian Vetta

Publikováno v: HAL
Symposium on Discrete Algorithms (SODA 2012)
Symposium on Discrete Algorithms (SODA 2012), Jan 2012, Kyoto, Japan

International audience; The Directed Steiner Tree (DST) problem is a cornerstone problem in network design, particularly, in the design of directed networks satisfying connectivity requirements. We focus on the generalization of the problem with high

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::a4be09b2ddb2f62d8e3072cf802dc94e
https://hal.science/hal-00709994

Maximum Flows on Disjoint Paths

Autor: Guyslain Naves, Adrian Vetta, Nicolas Sonnerat

Publikováno v: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
APPROX-RANDOM
APPROX-RANDOM, Sep 2010, Barcelona, Spain. pp.326-337, ⟨10.1007/978-3-642-15369-3_25⟩
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques ISBN: 9783642153686

International audience; We consider the question: What is the maximum flow achievable in a network if the flow must be decomposable into a collection of edge-disjoint paths? Equivalently, we wish to find a maximum weighted packing of disjoint paths,

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b5cf022a181c5c6b8b0636b7aeb6af70
https://hal.archives-ouvertes.fr/hal-00554467/file/dflows9.pdf