Zobrazeno 1 - 10
of 7 970
pro vyhledávání: '"[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]"'
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:
Pierre Lescanne
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 25:2 (2024)
Holonomic equations are recursive equations which allow computing efficiently numbers of combinatoric objects. Rémy showed that the holonomic equation associated with binary trees yields an efficient linear random generator of binary trees. I extend
Externí odkaz:
https://doaj.org/article/d9fd8077e1a34b0b9b9060144ab3e797
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 25:1, Iss Graph Theory (2023)
An s-branching flow f in a network N = (D, u), where u is the capacity function, is a flow thatreaches every vertex in V(D) from s while loosing exactly one unit of flow in each vertex other thans. Bang-Jensen and Bessy [TCS, 2014] showed that, when
Externí odkaz:
https://doaj.org/article/a061e59ab6c04f3d9bd882f1d0755459
Autor:
Simon Apers, Ronald de Wolf
Publikováno v:
2020 IEEE 61st Annual Symposium on Foundations of Computer Science: FOCS 2020 : proceedings : 16-19 November 2020, virtual conference, 637-648
STARTPAGE=637;ENDPAGE=648;TITLE=2020 IEEE 61st Annual Symposium on Foundations of Computer Science
FOCS
SIAM Journal on Computing, 51(6), 1703-1742
STARTPAGE=637;ENDPAGE=648;TITLE=2020 IEEE 61st Annual Symposium on Foundations of Computer Science
FOCS
SIAM Journal on Computing, 51(6), 1703-1742
Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, "spectral sparsification" reduces the number of edges to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::03af93c31c07159615f1a42b9c60f5b9
https://ir.cwi.nl/pub/32752
https://ir.cwi.nl/pub/32752
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 22 no. 3, Computational..., Iss Special issues (2021)
In this paper we address the problem of understanding Concurrency Theory from a combinatorial point of view. We are interested in quantitative results and algorithmic tools to refine our understanding of the classical combinatorial explosion phenomen
Externí odkaz:
https://doaj.org/article/d3fc0905b1b64835b81ebe8ec96db88d
Publikováno v:
ESA 2023-The 31st Annual European Symposium on Algorithms
ESA 2023-The 31st Annual European Symposium on Algorithms, Sep 2023, Amsterdam (Hollande), Netherlands
ESA 2023-The 31st Annual European Symposium on Algorithms, Sep 2023, Amsterdam (Hollande), Netherlands
International audience; We investigate the maximum bottleneck matching problem in bipartite graphs. Given a bipartite graph with nonnegative edge weights, the problem is to determine a maximum cardinality matching in which the minimum weight of an ed
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::002eeef63bf71a6021107d97ef9c06ba
https://inria.hal.science/hal-04146298
https://inria.hal.science/hal-04146298
Publikováno v:
Theoretical Computer Science
Theoretical Computer Science, In press, ⟨10.1016/j.tcs.2022.11.028⟩
Theoretical Computer Science, In press, ⟨10.1016/j.tcs.2022.11.028⟩
International audience; This paper proposes the first implementation of a self-stabilizing regular register emulated by n servers that is tolerant to both Mobile Byzantine Agents and transient failures in a round-free synchronous model. Differently f
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2da82602b71a38ddc2cdaacc78c203e1
https://doi.org/10.1016/j.tcs.2022.11.028
https://doi.org/10.1016/j.tcs.2022.11.028
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 21 no. 4, Iss Graph Theory (2019)
Power domination in graphs emerged from the problem of monitoring an electrical system by placing as few measurement devices in the system as possible. It corresponds to a variant of domination that includes the possibility of propagation. For measur
Externí odkaz:
https://doaj.org/article/f266aa89794e4037a80e0bc90b97966f
Publikováno v:
Future Generation Computer Systems
Future Generation Computer Systems, 2022, 130, pp.307-320. ⟨10.1016/j.future.2021.12.018⟩
[Research Report] RR-9368, INRIA. 2020
Future Generation Computer Systems, Elsevier, In press
Future Generation Computer Systems, 2022, 130, pp.307-320. ⟨10.1016/j.future.2021.12.018⟩
[Research Report] RR-9368, INRIA. 2020
Future Generation Computer Systems, Elsevier, In press
Sparse direct solvers using Block Low-Rank compression have been proven efficient to solve problems arising in many real-life applications. Improving those solvers is crucial for being able to 1) solve larger problems and 2) speed up computations. A
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f63db4c7540f15de729501627227b184
https://doi.org/10.1016/j.future.2021.12.018
https://doi.org/10.1016/j.future.2021.12.018
Autor:
Nicholas Coxon
Publikováno v:
Journal of Symbolic Computation. 110:66-80
We show that simple modifications to van der Hoeven's forward and inverse truncated Fourier transforms allow the algorithms to be performed in-place, and with only a linear overhead in complexity.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::9bc9d6711e0a8e6ab678009177054191
https://doi.org/10.1016/j.jsc.2021.10.002
https://doi.org/10.1016/j.jsc.2021.10.002