Zobrazeno 1 - 10
of 17
pro vyhledávání: '"Guyslain Naves"'
Autor:
Guyslain Naves, Bruce Shepherd
Publikováno v:
SIAM Journal on Discrete Mathematics. 36:1567-1585
Gomory-Hu (GH) Trees are a classical sparsification technique for graph connectivity. It is also a fundamental model in combinatorial optimization which finds new applications, for instance , finding highly-connected communities within (social) netwo
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
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
https://hal.archives-ouvertes.fr/hal-03514641/file/USRA_2020.pdf
Publikováno v:
Mathematical Programming
Mathematical Programming, 2022, ⟨10.1007/s10107-022-01780-0⟩
Mathematical Programming, 2022, ⟨10.1007/s10107-022-01780-0⟩
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___::af901f5e524ac9648a2818c150addd1e
http://arxiv.org/abs/2007.10537
http://arxiv.org/abs/2007.10537
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〉
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
https://hal.science/hal-03581534
Publikováno v:
Discrete & Computational Geometry. 53:16-37
In this paper, we prove that any non-positively curved 2-dimensional surface (alias, Busemann surface) is isometrically embeddable into $$L_1$$L1. As a corollary, we obtain that all planar graphs which are 1-skeletons of planar non-positively curved
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
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
Publikováno v:
ACM Transactions on Algorithms
ACM Transactions on Algorithms, Association for Computing Machinery, 2014, 11 (2), pp.8
ACM Transactions on Algorithms, 2014, 11 (2), pp.8
HAL
ACM Transactions on Algorithms, Association for Computing Machinery, 2014, 11 (2), pp.8
ACM Transactions on Algorithms, 2014, 11 (2), pp.8
HAL
The Directed Steiner Tree (DST) problem is a cornerstone problem in network design. We focus on the generalization of the problem with higher connectivity requirements. The problem with one root and two sinks is APX-hard. The problem with one root an
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1ce978b877a49b01613449780a924555
https://hal.archives-ouvertes.fr/hal-01198833
https://hal.archives-ouvertes.fr/hal-01198833
Publikováno v:
HAL
Symposium on Discrete Algorithms (SODA 2012)
Symposium on Discrete Algorithms (SODA 2012), Jan 2012, Kyoto, Japan
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
https://hal.science/hal-00709994
Publikováno v:
Internet and Network Economics
WINE 2012: The 8th Workshop on Internet & Network Economics
WINE 2012: The 8th Workshop on Internet & Network Economics, Dec 2012, University of Liverpool, United Kingdom
Springer Berlin Heidelberg
HAL
Lecture Notes in Computer Science ISBN: 9783642353109
WINE
WINE 2012: The 8th Workshop on Internet & Network Economics
WINE 2012: The 8th Workshop on Internet & Network Economics, Dec 2012, University of Liverpool, United Kingdom
Springer Berlin Heidelberg
HAL
Lecture Notes in Computer Science ISBN: 9783642353109
WINE
International audience; The second welfare theorem tells us that social welfare in an economy can be maximized at an equilibrium given a suitable redistribution of the endowments. We examine welfare maximization without redistribution. Specifically,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::91a25031a9c9ca5f1aea90f35e79f74a
https://hal.archives-ouvertes.fr/hal-01198790
https://hal.archives-ouvertes.fr/hal-01198790
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
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
https://hal.archives-ouvertes.fr/hal-00554467/file/dflows9.pdf