14 Search Results for "Viennot, Laurent"

Document
DOI: 10.4230/LIPIcs.ESA.2024.51
Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs

Authors: Lech Duraj, Filip Konieczny, and Krzysztof Potępa

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We develop a framework for algorithms finding the diameter in graphs of bounded distance Vapnik-Chervonenkis dimension, in (parameterized) subquadratic time complexity. The class of bounded distance VC-dimension graphs is wide, including, e.g. all minor-free graphs. We build on the work of Ducoffe et al. [SODA'20, SIGCOMP'22], improving their technique. With our approach the algorithms become simpler and faster, working in 𝒪{(k ⋅ n^{1-1/d} ⋅ m ⋅ polylog(n))} time complexity for the graph on n vertices and m edges, where k is the diameter and d is the distance VC-dimension of the graph. Furthermore, it allows us to use the improved technique in more general setting. In particular, we use this framework for geometric intersection graphs, i.e. graphs where vertices are identical geometric objects on a plane and the adjacency is defined by intersection. Applying our approach for these graphs, we partially answer a question posed by Bringmann et al. [SoCG'22], finding an 𝒪{(n^{7/4} ⋅ polylog(n))} parameterized diameter algorithm for unit square intersection graph of size n, as well as a more general algorithm for convex polygon intersection graphs.
Cite as

Lech Duraj, Filip Konieczny, and Krzysztof Potępa. Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{duraj_et_al:LIPIcs.ESA.2024.51,
  author =	{Duraj, Lech and Konieczny, Filip and Pot\k{e}pa, Krzysztof},
  title =	{{Better Diameter Algorithms for Bounded VC-Dimension Graphs and Geometric Intersection Graphs}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{51:1--51:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.51},
  URN =		{urn:nbn:de:0030-drops-211229},
  doi =		{10.4230/LIPIcs.ESA.2024.51},
  annote =	{Keywords: Graph Diameter, Geometric Intersection Graphs, Vapnik-Chervonenkis Dimension}
}
Document
DOI: 10.4230/LIPIcs.ESA.2024.84
Insights into (k, ρ)-Shortcutting Algorithms

Authors: Alexander Leonhardt, Ulrich Meyer, and Manuel Penschuck

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
A graph is called a (k, ρ)-graph iff every node can reach ρ of its nearest neighbors in at most k hops. This property has proven useful in the analysis and design of parallel shortest-path algorithms [Blelloch et al., 2016; Dong et al., 2021]. Any graph can be transformed into a (k, ρ)-graph by adding shortcuts. Formally, the (k,ρ)-Minimum-Shortcut-Problem (kρ-MSP) asks to find an appropriate shortcut set of minimal cardinality. We show that kρ-MSP is NP-complete in the practical regime of k ≥ 3 and ρ = Θ(n^ε) for ε > 0. With a related construction, we bound the approximation factor of known kρ-MSP heuristics [Blelloch et al., 2016] from below and propose algorithmic countermeasures improving the approximation quality. Further, we describe an integer linear problem (ILP) that optimally solves kρ-MSP. Finally, we compare the practical performance and quality of all algorithms empirically.
Cite as

Alexander Leonhardt, Ulrich Meyer, and Manuel Penschuck. Insights into (k, ρ)-Shortcutting Algorithms. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 84:1-84:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{leonhardt_et_al:LIPIcs.ESA.2024.84,
  author =	{Leonhardt, Alexander and Meyer, Ulrich and Penschuck, Manuel},
  title =	{{Insights into (k, \rho)-Shortcutting Algorithms}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{84:1--84:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.84},
  URN =		{urn:nbn:de:0030-drops-211554},
  doi =		{10.4230/LIPIcs.ESA.2024.84},
  annote =	{Keywords: Complexity, Approximation, Optimal algorithms, Parallel shortest path}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2024.18
Weighted Basic Parallel Processes and Combinatorial Enumeration

Authors: Lorenzo Clemente

Published in: LIPIcs, Volume 311, 35th International Conference on Concurrency Theory (CONCUR 2024)

Abstract
We study weighted basic parallel processes (WBPP), a nonlinear recursive generalisation of weighted finite automata inspired from process algebra and Petri net theory. Our main result is an algorithm of 2-EXPSPACE complexity for the WBPP equivalence problem. While (unweighted) BPP language equivalence is undecidable, we can use this algorithm to decide multiplicity equivalence of BPP and language equivalence of unambiguous BPP, with the same complexity. These are long-standing open problems for the related model of weighted context-free grammars. Our second contribution is a connection between WBPP, power series solutions of systems of polynomial differential equations, and combinatorial enumeration. To this end we consider constructible differentially finite power series (CDF), a class of multivariate differentially algebraic series introduced by Bergeron and Reutenauer in order to provide a combinatorial interpretation to differential equations. CDF series generalise rational, algebraic, and a large class of D-finite (holonomic) series, for which no complexity upper bound for equivalence was known. We show that CDF series correspond to commutative WBPP series. As a consequence of our result on WBPP and commutativity, we show that equivalence of CDF power series can be decided with 2-EXPTIME complexity. In order to showcase the CDF equivalence algorithm, we show that CDF power series naturally arise from combinatorial enumeration, namely as the exponential generating series of constructible species of structures. Examples of such species include sequences, binary trees, ordered trees, Cayley trees, set partitions, series-parallel graphs, and many others. As a consequence of this connection, we obtain an algorithm to decide multiplicity equivalence of constructible species, decidability of which was not known before. The complexity analysis is based on effective bounds from algebraic geometry, namely on the length of chains of polynomial ideals constructed by repeated application of finitely many, not necessarily commuting derivations of a multivariate polynomial ring. This is obtained by generalising a result of Novikov and Yakovenko in the case of a single derivation, which is noteworthy since generic bounds on ideal chains are non-primitive recursive in general. On the way, we develop the theory of WBPP series and CDF power series, exposing several of their appealing properties.
Cite as

Lorenzo Clemente. Weighted Basic Parallel Processes and Combinatorial Enumeration. In 35th International Conference on Concurrency Theory (CONCUR 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 311, pp. 18:1-18:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{clemente:LIPIcs.CONCUR.2024.18,
  author =	{Clemente, Lorenzo},
  title =	{{Weighted Basic Parallel Processes and Combinatorial Enumeration}},
  booktitle =	{35th International Conference on Concurrency Theory (CONCUR 2024)},
  pages =	{18:1--18:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-339-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{311},
  editor =	{Majumdar, Rupak and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2024.18},
  URN =		{urn:nbn:de:0030-drops-207903},
  doi =		{10.4230/LIPIcs.CONCUR.2024.18},
  annote =	{Keywords: weighted automata, combinatorial enumeration, shuffle, algebraic differential equations, process algebra, basic parallel processes, species of structures}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.12
Generalizing Roberts' Characterization of Unit Interval Graphs

Authors: Virginia Ardévol Martínez, Romeo Rizzi, Abdallah Saffidine, Florian Sikora, and Stéphane Vialette

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
For any natural number d, a graph G is a (disjoint) d-interval graph if it is the intersection graph of (disjoint) d-intervals, the union of d (disjoint) intervals on the real line. Two important subclasses of d-interval graphs are unit and balanced d-interval graphs (where every interval has unit length or all the intervals associated to a same vertex have the same length, respectively). A celebrated result by Roberts gives a simple characterization of unit interval graphs being exactly claw-free interval graphs. Here, we study the generalization of this characterization for d-interval graphs. In particular, we prove that for any d ⩾ 2, if G is a K_{1,2d+1}-free interval graph, then G is a unit d-interval graph. However, somehow surprisingly, under the same assumptions, G is not always a disjoint unit d-interval graph. This implies that the class of disjoint unit d-interval graphs is strictly included in the class of unit d-interval graphs. Finally, we study the relationships between the classes obtained under disjoint and non-disjoint d-intervals in the balanced case and show that the classes of disjoint balanced 2-intervals and balanced 2-intervals coincide, but this is no longer true for d > 2.
Cite as

Virginia Ardévol Martínez, Romeo Rizzi, Abdallah Saffidine, Florian Sikora, and Stéphane Vialette. Generalizing Roberts' Characterization of Unit Interval Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ardevolmartinez_et_al:LIPIcs.MFCS.2024.12,
  author =	{Ard\'{e}vol Mart{\'\i}nez, Virginia and Rizzi, Romeo and Saffidine, Abdallah and Sikora, Florian and Vialette, St\'{e}phane},
  title =	{{Generalizing Roberts' Characterization of Unit Interval Graphs}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.12},
  URN =		{urn:nbn:de:0030-drops-205687},
  doi =		{10.4230/LIPIcs.MFCS.2024.12},
  annote =	{Keywords: Interval graphs, Multiple Interval Graphs, Unit Interval Graphs, Characterization}
}
Document
DOI: 10.4230/LIPIcs.SEA.2024.6
Faster Treewidth-Based Approximations for Wiener Index

Authors: Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit Jitendra Motwani

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
The Wiener index of a graph G is the sum of distances between all pairs of its vertices. It is a widely-used graph property in chemistry, initially introduced to examine the link between boiling points and structural properties of alkanes, which later found notable applications in drug design. Thus, computing or approximating the Wiener index of molecular graphs, i.e. graphs in which every vertex models an atom of a molecule and every edge models a bond, is of significant interest to the computational chemistry community. In this work, we build upon the observation that molecular graphs are sparse and tree-like and focus on developing efficient algorithms parameterized by treewidth to approximate the Wiener index. We present a new randomized approximation algorithm using a combination of tree decompositions and centroid decompositions. Our algorithm approximates the Wiener index within any desired multiplicative factor (1 ± ε) in time O(n ⋅ log n ⋅ k³ + √n ⋅ k/ε²), where n is the number of vertices of the graph and k is the treewidth. This time bound is almost-linear in n. Finally, we provide experimental results over standard benchmark molecules from PubChem and the Protein Data Bank, showcasing the applicability and scalability of our approach on real-world chemical graphs and comparing it with previous methods.
Cite as

Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit Jitendra Motwani. Faster Treewidth-Based Approximations for Wiener Index. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{conrado_et_al:LIPIcs.SEA.2024.6,
  author =	{Conrado, Giovanna Kobus and Goharshady, Amir Kafshdar and Hudec, Pavel and Li, Pingjiang and Motwani, Harshit Jitendra},
  title =	{{Faster Treewidth-Based Approximations for Wiener Index}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.6},
  URN =		{urn:nbn:de:0030-drops-203718},
  doi =		{10.4230/LIPIcs.SEA.2024.6},
  annote =	{Keywords: Computational Chemistry, Treewidth, Wiener Index}
}
Document
DOI: 10.4230/LIPIcs.SEA.2024.8
Practical Computation of Graph VC-Dimension

Authors: David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
For any set system ℋ = (V,ℛ), ℛ ⊆ 2^V, a subset S ⊆ V is called shattered if every S' ⊆ S results from the intersection of S with some set in ℛ. The VC-dimension of ℋ is the size of a largest shattered set in V. In this paper, we focus on the problem of computing the VC-dimension of graphs. In particular, given a graph G = (V,E), the VC-dimension of G is defined as the VC-dimension of (V, N), where N contains each subset of V that can be obtained as the closed neighborhood of some vertex v ∈ V in G. Our main contribution is an algorithm for computing the VC-dimension of any graph, whose effectiveness is shown through experiments on various types of practical graphs, including graphs with millions of vertices. A key aspect of its efficiency resides in the fact that practical graphs have small VC-dimension, up to 8 in our experiments. As a side-product, we present several new bounds relating the graph VC-dimension to other classical graph theoretical notions. We also establish the W[1]-hardness of the graph VC-dimension problem by extending a previous result for arbitrary set systems.
Cite as

David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot. Practical Computation of Graph VC-Dimension. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{coudert_et_al:LIPIcs.SEA.2024.8,
  author =	{Coudert, David and Csik\'{o}s, M\'{o}nika and Ducoffe, Guillaume and Viennot, Laurent},
  title =	{{Practical Computation of Graph VC-Dimension}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.8},
  URN =		{urn:nbn:de:0030-drops-203731},
  doi =		{10.4230/LIPIcs.SEA.2024.8},
  annote =	{Keywords: VC-dimension, graph, algorithm}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.13
Temporalizing Digraphs via Linear-Size Balanced Bi-Trees

Authors: Stéphane Bessy, Stéphan Thomassé, and Laurent Viennot

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
In a directed graph D on vertex set v₁,… ,v_n, a forward arc is an arc v_iv_j where i < j. A pair v_i,v_j is forward connected if there is a directed path from v_i to v_j consisting of forward arcs. In the Forward Connected Pairs Problem (FCPP), the input is a strongly connected digraph D, and the output is the maximum number of forward connected pairs in some vertex enumeration of D. We show that FCPP is in APX, as one can efficiently enumerate the vertices of D in order to achieve a quadratic number of forward connected pairs. For this, we construct a linear size balanced bi-tree T (an out-branching and an in-branching with same size and same root which are vertex disjoint in the sense that they share no vertex apart from their common root). The existence of such a T was left as an open problem (Brunelli, Crescenzi, Viennot, Networks 2023) motivated by the study of temporal paths in temporal networks. More precisely, T can be constructed in quadratic time (in the number of vertices) and has size at least n/3. The algorithm involves a particular depth-first search tree (Left-DFS) of independent interest, and shows that every strongly connected directed graph has a balanced separator which is a circuit. Remarkably, in the request version RFCPP of FCPP, where the input is a strong digraph D and a set of requests R consisting of pairs {x_i,y_i}, there is no constant c > 0 such that one can always find an enumeration realizing c.|R| forward connected pairs {x_i,y_i} (in either direction).
Cite as

Stéphane Bessy, Stéphan Thomassé, and Laurent Viennot. Temporalizing Digraphs via Linear-Size Balanced Bi-Trees. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 13:1-13:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bessy_et_al:LIPIcs.STACS.2024.13,
  author =	{Bessy, St\'{e}phane and Thomass\'{e}, St\'{e}phan and Viennot, Laurent},
  title =	{{Temporalizing Digraphs via Linear-Size Balanced Bi-Trees}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{13:1--13:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.13},
  URN =		{urn:nbn:de:0030-drops-197235},
  doi =		{10.4230/LIPIcs.STACS.2024.13},
  annote =	{Keywords: digraph, temporal graph, temporalization, bi-tree, #1\{in-branching, out-branching, in-tree, out-tree\}, forward connected pairs, left-maximal DFS}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.35
Collective Tree Exploration via Potential Function Method

Authors: Romain Cosson and Laurent Massoulié

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
We study the problem of collective tree exploration (CTE) in which a team of k agents is tasked to traverse all the edges of an unknown tree as fast as possible, assuming complete communication between the agents [FGKP06]. In this paper, we present an algorithm performing collective tree exploration in 2n/k+𝒪(kD) rounds, where n is the number of nodes in the tree, and D is the tree depth. This leads to a competitive ratio of 𝒪(√k), the first polynomial improvement over the 𝒪(k) ratio of depth-first search. Our analysis holds for an asynchronous generalization of collective tree exploration. It relies on a game with robots at the leaves of a continuously growing tree extending the "tree-mining game" of [C23] and resembling the "evolving tree game" of [BCR22]. Another surprising consequence of our results is the existence of algorithms {𝒜_k}_{k ∈ ℕ} for layered tree traversal (LTT) with cost at most 2L/k+𝒪(kD), where L is the sum of all edge lengths. For the case of layered trees of width w and unit edge lengths, our guarantee is thus in 𝒪(√wD).
Cite as

Romain Cosson and Laurent Massoulié. Collective Tree Exploration via Potential Function Method. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 35:1-35:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cosson_et_al:LIPIcs.ITCS.2024.35,
  author =	{Cosson, Romain and Massouli\'{e}, Laurent},
  title =	{{Collective Tree Exploration via Potential Function Method}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{35:1--35:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.35},
  URN =		{urn:nbn:de:0030-drops-195638},
  doi =		{10.4230/LIPIcs.ITCS.2024.35},
  annote =	{Keywords: collective exploration, online algorithms, evolving tree, competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.14
Efficient Collaborative Tree Exploration with Breadth-First Depth-Next

Authors: Romain Cosson, Laurent Massoulié, and Laurent Viennot

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
We study the problem of collaborative tree exploration introduced by Fraigniaud, Gasieniec, Kowalski, and Pelc [Pierre Fraigniaud et al., 2006] where a team of k agents is tasked to collectively go through all the edges of an unknown tree as fast as possible and return to the root. Denoting by n the total number of nodes and by D the tree depth, the 𝒪(n/log(k)+D) algorithm of [Pierre Fraigniaud et al., 2006] achieves a 𝒪(k/log(k)) competitive ratio with respect to the cost of offline exploration which is at least max{{2n/k,2D}}. Brass, Cabrera-Mora, Gasparri, and Xiao [Peter Brass et al., 2011] study an alternative performance criterion, the competitive overhead with respect to the cost of offline exploration, with their 2n/k+𝒪((D+k)^k) guarantee. In this paper, we introduce "Breadth-First Depth-Next" (BFDN), a novel and simple algorithm that performs collaborative tree exploration in 2n/k+𝒪(D²log(k)) rounds, thus outperforming [Peter Brass et al., 2011] for all values of (n,D,k) and being order-optimal for trees of depth D = o(√n). Our analysis relies on a two-player game reflecting a problem of online resource allocation that could be of independent interest. We extend the guarantees of BFDN to: scenarios with limited memory and communication, adversarial setups where robots can be blocked, and exploration of classes of non-tree graphs. Finally, we provide a recursive version of BFDN with a runtime of 𝒪_𝓁(n/k^{1/𝓁}+log(k) D^{1+1/𝓁}) for parameter 𝓁 ≥ 1, thereby improving performance for trees with large depth.
Cite as

Romain Cosson, Laurent Massoulié, and Laurent Viennot. Efficient Collaborative Tree Exploration with Breadth-First Depth-Next. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 14:1-14:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{cosson_et_al:LIPIcs.DISC.2023.14,
  author =	{Cosson, Romain and Massouli\'{e}, Laurent and Viennot, Laurent},
  title =	{{Efficient Collaborative Tree Exploration with Breadth-First Depth-Next}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{14:1--14:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.14},
  URN =		{urn:nbn:de:0030-drops-191409},
  doi =		{10.4230/LIPIcs.DISC.2023.14},
  annote =	{Keywords: collaborative exploration, online algorithms, trees, adversarial game, competitive analysis, robot swarms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.37
Revisiting the Random Subset Sum Problem

Authors: Arthur Carvalho Walraven Da Cunha, Francesco d'Amore, Frédéric Giroire, Hicham Lesfari, Emanuele Natale, and Laurent Viennot

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
The average properties of the well-known Subset Sum Problem can be studied by means of its randomised version, where we are given a target value z, random variables X_1, …, X_n, and an error parameter ε > 0, and we seek a subset of the X_is whose sum approximates z up to error ε. In this setup, it has been shown that, under mild assumptions on the distribution of the random variables, a sample of size 𝒪(log(1/ε)) suffices to obtain, with high probability, approximations for all values in [-1/2, 1/2]. Recently, this result has been rediscovered outside the algorithms community, enabling meaningful progress in other fields. In this work, we present an alternative proof for this theorem, with a more direct approach and resourcing to more elementary tools.
Cite as

Arthur Carvalho Walraven Da Cunha, Francesco d'Amore, Frédéric Giroire, Hicham Lesfari, Emanuele Natale, and Laurent Viennot. Revisiting the Random Subset Sum Problem. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 37:1-37:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dacunha_et_al:LIPIcs.ESA.2023.37,
  author =	{Da Cunha, Arthur Carvalho Walraven and d'Amore, Francesco and Giroire, Fr\'{e}d\'{e}ric and Lesfari, Hicham and Natale, Emanuele and Viennot, Laurent},
  title =	{{Revisiting the Random Subset Sum Problem}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{37:1--37:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.37},
  URN =		{urn:nbn:de:0030-drops-186905},
  doi =		{10.4230/LIPIcs.ESA.2023.37},
  annote =	{Keywords: Random subset sum, Randomised method, Subset-sum, Combinatorics}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.4
Computing Temporal Reachability Under Waiting-Time Constraints in Linear Time

Authors: Filippo Brunelli and Laurent Viennot

Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

Abstract
This paper proposes a simple algorithm for computing single-source reachability in a temporal graph under waiting-time constraints, that is when waiting at each node is bounded by some time constraints. Given a space-time representation of a temporal graph, and a source node, the algorithm computes in linear-time which nodes and temporal edges are reachable through a constrained temporal walk from the source.
Cite as

Filippo Brunelli and Laurent Viennot. Computing Temporal Reachability Under Waiting-Time Constraints in Linear Time. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 4:1-4:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{brunelli_et_al:LIPIcs.SAND.2023.4,
  author =	{Brunelli, Filippo and Viennot, Laurent},
  title =	{{Computing Temporal Reachability Under Waiting-Time Constraints in Linear Time}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{4:1--4:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.4},
  URN =		{urn:nbn:de:0030-drops-179402},
  doi =		{10.4230/LIPIcs.SAND.2023.4},
  annote =	{Keywords: temporal reachability, temporal graph, temporal path, temporal walk, waiting-time constraints, restless temporal walk, linear time}
}
Document
DOI: 10.4230/LIPIcs.SEA.2021.11
On Computing the Diameter of (Weighted) Link Streams

Authors: Marco Calamai, Pierluigi Crescenzi, and Andrea Marino

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract
A weighted link stream is a pair (V,𝔼) comprising V, the set of nodes, and 𝔼, the list of temporal edges (u,v,t,λ), where u,v are two nodes in V, t is the starting time of the temporal edge, and λ is its travel time. By making use of this model, different notions of diameter can be defined, which refer to the following distances: earliest arrival time, latest departure time, fastest time, and shortest time. After proving that any of these diameters cannot be computed in time sub-quadratic with respect to the number of temporal edges, we propose different algorithms (inspired by the approach used for computing the diameter of graphs) which allow us to compute, in practice very efficiently, the diameter of quite large real-world weighted link stream for several definitions of the diameter. Indeed, all the proposed algorithms require very often a very low number of single source (or target) best path computations. We verify the effectiveness of our approach by means of an extensive set of experiments on real-world link streams. We also experimentally prove that the temporal version of the well-known 2-sweep technique, for computing a lower bound on the diameter of a graph, is quite effective in the case of weighted link stream, by returning very often tight bounds.
Cite as

Marco Calamai, Pierluigi Crescenzi, and Andrea Marino. On Computing the Diameter of (Weighted) Link Streams. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{calamai_et_al:LIPIcs.SEA.2021.11,
  author =	{Calamai, Marco and Crescenzi, Pierluigi and Marino, Andrea},
  title =	{{On Computing the Diameter of (Weighted) Link Streams}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{11:1--11:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.11},
  URN =		{urn:nbn:de:0030-drops-137836},
  doi =		{10.4230/LIPIcs.SEA.2021.11},
  annote =	{Keywords: Temporal graph, shortest path, diameter}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.143
Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond

Authors: Siddharth Gupta, Adrian Kosowski, and Laurent Viennot

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
For fixed h >= 2, we consider the task of adding to a graph G a set of weighted shortcut edges on the same vertex set, such that the length of a shortest h-hop path between any pair of vertices in the augmented graph is exactly the same as the original distance between these vertices in G. A set of shortcut edges with this property is called an exact h-hopset and may be applied in processing distance queries on graph G. In particular, a 2-hopset directly corresponds to a distributed distance oracle known as a hub labeling. In this work, we explore centralized distance oracles based on 3-hopsets and display their advantages in several practical scenarios. In particular, for graphs of constant highway dimension, and more generally for graphs of constant skeleton dimension, we show that 3-hopsets require exponentially fewer shortcuts per node than any previously described distance oracle, and also offer a speedup in query time when compared to simple oracles based on a direct application of 2-hopsets. Finally, we consider the problem of computing minimum-size h-hopset (for any h >= 2) for a given graph G, showing a polylogarithmic-factor approximation for the case of unique shortest path graphs. When h=3, for a given bound on the space used by the distance oracle, we provide a construction of hopset achieving polylog approximation both for space and query time compared to the optimal 3-hopset oracle given the space bound.
Cite as

Siddharth Gupta, Adrian Kosowski, and Laurent Viennot. Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 143:1-143:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.ICALP.2019.143,
  author =	{Gupta, Siddharth and Kosowski, Adrian and Viennot, Laurent},
  title =	{{Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{143:1--143:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.143},
  URN =		{urn:nbn:de:0030-drops-107199},
  doi =		{10.4230/LIPIcs.ICALP.2019.143},
  annote =	{Keywords: Hopsets, Distance Oracles, Graph Algorithms, Data Structures}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.15
Decomposing a Graph into Shortest Paths with Bounded Eccentricity

Authors: Etienne Birmelé, Fabien de Montgolfier, Léo Planche, and Laurent Viennot

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
We introduce the problem of hub-laminar decomposition which generalizes that of computing a shortest path with minimum eccentricity (MESP). Intuitively, it consists in decomposing a graph into several paths that collectively have small eccentricity and meet only near their extremities. The problem is related to computing an isometric cycle with minimum eccentricity (MEIC). It is also linked to DNA reconstitution in the context of metagenomics in biology. We show that a graph having such a decomposition with long enough paths can be decomposed in polynomial time with approximated guaranties on the parameters of the decomposition. Moreover, such a decomposition with few paths allows to compute a compact representation of distances with additive distortion. We also show that having an isometric cycle with small eccentricity is related to the possibility of embedding the graph in a cycle with low distortion.
Cite as

Etienne Birmelé, Fabien de Montgolfier, Léo Planche, and Laurent Viennot. Decomposing a Graph into Shortest Paths with Bounded Eccentricity. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{birmele_et_al:LIPIcs.ISAAC.2017.15,
  author =	{Birmel\'{e}, Etienne and de Montgolfier, Fabien and Planche, L\'{e}o and Viennot, Laurent},
  title =	{{Decomposing a Graph into Shortest Paths with Bounded Eccentricity}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.15},
  URN =		{urn:nbn:de:0030-drops-82621},
  doi =		{10.4230/LIPIcs.ISAAC.2017.15},
  annote =	{Keywords: Graph Decomposition, Graph Clustering, Distance Labeling, BFS, MESP}
}
  • Refine by Author
  • 7 Viennot, Laurent
  • 2 Cosson, Romain
  • 2 Massoulié, Laurent
  • 1 Ardévol Martínez, Virginia
  • 1 Bessy, Stéphane
  • Show More...

  • Refine by Classification
  • 5 Mathematics of computing → Graph algorithms
  • 3 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Online algorithms
  • 2 Theory of computation → Parameterized complexity and exact algorithms
  • 2 Theory of computation → Shortest paths
  • Show More...

  • Refine by Keyword
  • 2 competitive analysis
  • 2 online algorithms
  • 2 temporal graph
  • 1 #1{in-branching
  • 1 Approximation
  • Show More...

  • Refine by Type
  • 14 document

  • Refine by Publication Year
  • 8 2024
  • 3 2023
  • 1 2017
  • 1 2019
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact