Zobrazeno 1 - 10
of 33
pro vyhledávání: '"Guillaume Ducoffe"'
Autor:
Guillaume DUCOFFE
Publikováno v:
Revista Română de Informatică și Automatică, Vol 34, Iss 1, Pp 59-68 (2024)
Thanks to the European recovery instrument "NGEU", there are several opportunities to finance new infrastructures in the EU member states. For this reason, based on graph theory, a preliminary analysis of the transport network in Bucharest is propose
Externí odkaz:
https://doaj.org/article/04db6031813e4fbd86b25898a77f0a30
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 26:2, Iss Graph Theory (2024)
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 sl
Externí odkaz:
https://doaj.org/article/c6b05094c92c467a8005398f1f2edce5
Autor:
Guillaume DUCOFFE
Publikováno v:
Revista Română de Informatică și Automatică, Vol 32, Iss 4, Pp 33-44 (2022)
Food webs, some scheduling problems and DNA molecules all have in common a “linear structure” which can be captured through the idealized model of interval graphs (intersection graphs of intervals on a line). However, real data is prone to errors
Externí odkaz:
https://doaj.org/article/caa54a370dd94809a76aa62950558f5d
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 23, no. 3, Iss Graph Theory (2021)
When can we compute the diameter of a graph in quasi linear time? We address this question for the class of {\em split graphs}, that we observe to be the hardest instances for deciding whether the diameter is at most two. We stress that although the
Externí odkaz:
https://doaj.org/article/1c9e676c04af48b89ce3b22bab9c6174
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 20 no. 1, Iss Graph Theory (2018)
Recently, Araujo et al. [Manuscript in preparation, 2017] introduced the notion of Cycle Convexity of graphs. In their seminal work, they studied the graph convexity parameter called hull number for this new graph convexity they proposed, and they pr
Externí odkaz:
https://doaj.org/article/f61ba853d71e4b7780b66619d792d4b1
Autor:
Guillaume DUCOFFE
Publikováno v:
Revista Română de Informatică și Automatică. 32:33-44
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::daada974960673656952b8d0f9679c14
https://doi.org/10.33436/v32i4y202203
https://doi.org/10.33436/v32i4y202203
Publikováno v:
SIAM Journal on Computing. 51:1506-1534
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::60c6fb0d7b71666553d1d080a83a54a2
https://doi.org/10.1137/20m136551x
https://doi.org/10.1137/20m136551x
Autor:
Guillaume Ducoffe, Feodor F. Dragan
Publikováno v:
Networks. 77:435-453
We present new algorithmic results for the class of Helly graphs, i.e., for the discrete analogues of hyperconvex metric spaces. Specifically, an undirected unweighted graph is Helly if every family of pairwise intersecting balls has a nonempty commo
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::8a9d8ea297296e5896d98ba691f02da8
https://doi.org/10.1002/net.21998
https://doi.org/10.1002/net.21998
Autor:
Guillaume Ducoffe
Publikováno v:
Graph-Theoretic Concepts in Computer Science (WG 2021)
47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2021)
47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2021), Jun 2021, Warsaw (online), Poland. pp.321-335, ⟨10.1007/978-3-030-86838-3_25⟩
Graph-Theoretic Concepts in Computer Science ISBN: 9783030868376
WG
47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2021)
47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2021), Jun 2021, Warsaw (online), Poland. pp.321-335, ⟨10.1007/978-3-030-86838-3_25⟩
Graph-Theoretic Concepts in Computer Science ISBN: 9783030868376
WG
Characterizing the graph classes such that, on $n$-vertex $m$-edge graphs in the class, we can compute the diameter faster than in ${\cal O}(nm)$ time is an important research problem both in theory and in practice. We here make a new step in this di
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9dc1a3b86414964922a5eda86dee32d4
https://hal.archives-ouvertes.fr/hal-03350582/document
https://hal.archives-ouvertes.fr/hal-03350582/document
Autor:
Arne Leitert, Guillaume Ducoffe
Publikováno v:
Discrete Applied Mathematics
Discrete Applied Mathematics, Elsevier, 2019, 262, pp.185-188. ⟨10.1016/j.dam.2019.02.009⟩
Discrete Applied Mathematics, Elsevier, 2019, 262, pp.185-188. ⟨10.1016/j.dam.2019.02.009⟩
We say that a given graph G = ( V , E ) has pathbreadth at most ρ , denoted pb ( G ) ≤ ρ , if there exists a Robertson and Seymour’s path decomposition where every bag is contained in the ρ -neighbourhood of some vertex. Similarly, we say that
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1b423ec86af8a1c3c8d36513af4482a3
https://doi.org/10.1016/j.dam.2019.02.009
https://doi.org/10.1016/j.dam.2019.02.009