Zobrazeno 1 - 10
of 127
pro vyhledávání: '"Cyril Gavoille"'
Autor:
Cyril Gavoille, Nicolas Hanusse
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 10 no. 3 (2008)
In this paper we show an information-theoretic lower bound of kn - o(kn) on the minimum number of bits to represent an unlabeled simple connected n-node graph of pagenumber k. This has to be compared with the efficient encoding scheme of Munro and Ra
Externí odkaz:
https://doaj.org/article/8027c3fb13d44f37ba793ae61fd7f30c
Publikováno v:
SIAM Journal on Discrete Mathematics
SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2021, 35 (2), pp.1224-1237. ⟨10.1137/21M1406155⟩
SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2021, 35 (2), pp.1224-1237. ⟨10.1137/21M1406155⟩
A subgraph $H$ of a graph $G$ is isometric if the distances between vertices in $H$ coincide with the distances between the corresponding vertices in $G$. We show that for any integer $n\ge 1$, there is a graph on $3^{n+O(\log^2 n)}$ vertices that co
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::65f20a70328fa353be9ff6c564ba67b7
Autor:
Cyril Gavoille, Youssou Dieng
Publikováno v:
Innovations and Interdisciplinary Solutions for Underserved Areas ISBN: 9783030510503
InterSol
InterSol
We study in this article, the treewidth of planar graphs excluding as minor a fixed planar graph. We prove that the treewidth of every planar graph excluding a graph having a poly-line \(p \times q\)-grid drawing is \(O(p\sqrt{q})\). As consequences,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8e3e58cf216a9beba2181d23345b31df
https://doi.org/10.1007/978-3-030-51051-0_17
https://doi.org/10.1007/978-3-030-51051-0_17
Publikováno v:
Combinatorics on Words
Combinatorics on Words, pp.193-206, 2019, ⟨10.1007/978-3-030-28796-2_15⟩
Lecture Notes in Computer Science ISBN: 9783030287955
WORDS
Combinatorics on Words, pp.193-206, 2019, ⟨10.1007/978-3-030-28796-2_15⟩
Lecture Notes in Computer Science ISBN: 9783030287955
WORDS
We consider q-coloured words, that is words on \(\left\{ {{1},\dots ,{q}}\right\} \) where no two consecutive letters are equal. Motivated by multipartite colouring games with nonsignalling resources, we are interested in random q-coloured words sati
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1dce7775b406ef38fb51e64419061f86
https://hal.archives-ouvertes.fr/hal-02480563
https://hal.archives-ouvertes.fr/hal-02480563
Autor:
Christian Barillot, Inbar Fijalkow, Isabelle Queinnec, Fabrice Theoleyre, Hélène Touzet, Michel Beaudouin-Lafon, Marie-Paule Cani, François Chaumette, Gérald Conreur, Véronique Cortier, Cyril Gavoille, Guy Gogniat, Julien Gossa, Andreas Herzig, Jean Krivine, Philippe Lamarre, Françoise Lamnabhi-Lagarrigue, Anne-Catherine Letournel, Lionel Seinturier, Isabelle Tellier, Serge Torres, Charlotte Truchet, Alexandros Tsoukias, Michel Verleysen
Publikováno v:
[0] CNRS. 2018, pp.1-87
HAL
[Autre] CNRS. 2018, pp.1-87
HAL
[Autre] CNRS. 2018, pp.1-87
The production of a scientific prospective report corresponds to one of the missions of the Institutes Scientific Councils (CSI) of CNRS. Such a report is both for internal use by the CNRS (the head of the institution, institutes, national review com
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::6135eb9a297475fedf8e75740da2a5a8
https://hal.science/hal-01956087
https://hal.science/hal-01956087
Publikováno v:
Computational Geometry. 48:237-250
In this paper we determine the stretch factor of the $L_1$-Delaunay and $L_\infty$-Delaunay triangulations, and we show that this stretch is $\sqrt{4+2\sqrt{2}} \approx 2.61$. Between any two points $x,y$ of such triangulations, we construct a path w
Autor:
Cyril Gavoille, David Ilcinkas
This book constitutes the proceedings of the 30th International Symposium on Distributed Computing, DISC 2016, held in Paris, France, in September 2016. The 32 full papers, 10 brief annoucements and 3 invited lectures presented in this volume were ca
Autor:
Stefan Göller, Christoph Haase, Joel Ouaknine, James Worrell, Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, Paul G. Spirakis
Publikováno v:
Automata, Languages and Programming ISBN: 9783642141614
ICALP (2)
ICALP (2)
We investigate the decidability and complexity of various model checking problems over one-counter automata. More specifically, we consider succinct one-counter automata, in which additive updates are encoded in binary, as well as parametric one-coun
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6fdc97107da6254da0657862950526dd
https://ora.ox.ac.uk/objects/uuid:0cf27bce-e14f-47c5-9b02-d367c1a1893a
https://ora.ox.ac.uk/objects/uuid:0cf27bce-e14f-47c5-9b02-d367c1a1893a
Autor:
David Ilcinkas, Cyril Gavoille
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783662534250
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6280a6a39fc3a513f8a8330458453fa3
https://doi.org/10.1007/978-3-662-53426-7
https://doi.org/10.1007/978-3-662-53426-7