127 Search Results for "Spirakis, Paul"

Volume

LIPIcs, Volume 257

2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)

SAND 2023, June 19-21, 2023, Pisa, Italy

Editors: David Doty and Paul Spirakis

Volume

LIPIcs, Volume 117

43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

MFCS 2018, August 27-31, 2018, Liverpool, GB

Editors: Igor Potapov, Paul Spirakis, and James Worrell

Document
Invited Talk
DOI: 10.4230/LIPIcs.MFCS.2023.5
Sliding into the Future: Investigating Sliding Windows in Temporal Graphs (Invited Talk)

Authors: Nina Klobas, George B. Mertzios, and Paul G. Spirakis

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Graphs are fundamental tools for modelling relations among objects in various scientific fields. However, traditional static graphs have limitations when it comes to capturing the dynamic nature of real-world systems. To overcome this limitation, temporal graphs have been introduced as a framework to model graphs that change over time. In temporal graphs the edges among vertices appear and disappear at specific time steps, reflecting the temporal dynamics of the observed system, which allows us to analyse time dependent patterns and processes. In this paper we focus on the research related to sliding time windows in temporal graphs. Sliding time windows offer a way to analyse specific time intervals within the lifespan of a temporal graph. By sliding the window along the timeline, we can examine the graph’s characteristics and properties within different time periods. This paper provides an overview of the research on sliding time windows in temporal graphs. Although progress has been made in this field, there are still many interesting questions and challenges to be explored. We discuss some of the open problems and highlight their potential for future research.
Cite as

Nina Klobas, George B. Mertzios, and Paul G. Spirakis. Sliding into the Future: Investigating Sliding Windows in Temporal Graphs (Invited Talk). In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{klobas_et_al:LIPIcs.MFCS.2023.5,
  author =	{Klobas, Nina and Mertzios, George B. and Spirakis, Paul G.},
  title =	{{Sliding into the Future: Investigating Sliding Windows in Temporal Graphs}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{5:1--5:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.5},
  URN =		{urn:nbn:de:0030-drops-185397},
  doi =		{10.4230/LIPIcs.MFCS.2023.5},
  annote =	{Keywords: Temporal Graphs, Sliding Time Windows}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.SAND.2023
LIPIcs, Volume 257, SAND 2023, Complete Volume

Authors: David Doty and Paul Spirakis

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

Abstract
LIPIcs, Volume 257, SAND 2023, Complete Volume
Cite as

2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 1-278, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{doty_et_al:LIPIcs.SAND.2023,
  title =	{{LIPIcs, Volume 257, SAND 2023, Complete Volume}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{1--278},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023},
  URN =		{urn:nbn:de:0030-drops-179357},
  doi =		{10.4230/LIPIcs.SAND.2023},
  annote =	{Keywords: LIPIcs, Volume 257, SAND 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.SAND.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: David Doty and Paul Spirakis

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

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 0:i-0:x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{doty_et_al:LIPIcs.SAND.2023.0,
  author =	{Doty, David and Spirakis, Paul},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{0:i--0:x},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.0},
  URN =		{urn:nbn:de:0030-drops-179367},
  doi =		{10.4230/LIPIcs.SAND.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.1
Snapshot Disjointness in Temporal Graphs

Authors: Allen Ibiapina and Ana Silva

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

Abstract
In the study of temporal graphs, only paths respecting the flow of time are relevant. In this context, many concepts of walks disjointness have been proposed over the years, and the validity of Menger’s Theorem, as well as the complexity of related problems, has been investigated. Menger’s Theorem states that the maximum number of disjoint paths between two vertices is equal to the minimum number of vertices required to disconnect them. In this paper, we introduce and investigate a type of disjointness that is only time dependent. Two walks are said to be snapshot disjoint if they are not active in a same snapshot (also called timestep). The related paths and cut problems are then defined and proved to be W[1]-hard and XP-time solvable when parameterized by the size of the solution. Additionally, in the light of the definition of Mengerian graphs given by Kempe, Kleinberg and Kumar in their seminal paper (STOC'2000), we define a Mengerian graph for time as a graph G for which there is no time labeling for its edges where Menger’s Theorem does not hold in the context of snapshot disjointness. We then give a characterization of Mengerian graphs in terms of forbidden structures and provide a polynomial-time recognition algorithm. Finally, we also prove that, given a temporal graph (G,λ) and a pair of vertices s,z ∈ V(G), deciding whether at most h multiedges can separate s from z is NP-complete, where one multiedge uv is the set of all edges with endpoints u and v.
Cite as

Allen Ibiapina and Ana Silva. Snapshot Disjointness in Temporal Graphs. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ibiapina_et_al:LIPIcs.SAND.2023.1,
  author =	{Ibiapina, Allen and Silva, Ana},
  title =	{{Snapshot Disjointness in Temporal Graphs}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{1:1--1:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.1},
  URN =		{urn:nbn:de:0030-drops-179379},
  doi =		{10.4230/LIPIcs.SAND.2023.1},
  annote =	{Keywords: Temporal graphs, Menger’s Theorem, Snapshot disjointness}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.2
Partial Gathering of Mobile Agents in Dynamic Tori

Authors: Masahiro Shibata, Naoki Kitamura, Ryota Eguchi, Yuichi Sudo, Junya Nakamura, and Yonghwan Kim

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

Abstract
In this paper, we consider the partial gathering problem of mobile agents in synchronous dynamic tori. The partial gathering problem is a generalization of the (well-investigated) total gathering problem, which requires that all k agents distributed in the network terminate at a non-predetermined single node. The partial gathering problem requires, for a given positive integer g (< k), that agents terminate in a configuration such that either at least g agents or no agent exists at each node. So far, in almost cases, the partial gathering problem has been considered in static graphs. As only one exception, it is considered in a kind of dynamic rings called 1-interval connected rings, that is, one of the links in the ring may be missing at each time step. In this paper, we consider partial gathering in another dynamic topology. Concretely, we consider it in n× n dynamic tori such that each of row rings and column rings is represented as a 1-interval connected ring. In such networks, when k = O(gn), focusing on the relationship between the values of k, n, and g, we aim to characterize the solvability of the partial gathering problem and analyze the move complexity of the proposed algorithms when the problem can be solved. First, we show that agents cannot solve the problem when k = o(gn), which means that Ω (gn) agents are necessary to solve the problem. Second, we show that the problem can be solved with the total number of O(gn³) moves when 2gn+2n-1 ≤ k ≤ 2gn + 6n +16g -12. Finally, we show that the problem can be solved with the total number of O(gn²) moves when k ≥ 2gn + 6n +16g -11. From these results, we show that our algorithms can solve the partial gathering problem in dynamic tori with the asymptotically optimal number Θ (gn) of agents. In addition, we show that agents require a total number of Ω(gn²) moves to solve the partial gathering problem in dynamic tori when k = Θ(gn). Thus, when k ≥ 2gn+6n+16g -11, our algorithm can solve the problem with asymptotically optimal number O(gn²) of agent moves.
Cite as

Masahiro Shibata, Naoki Kitamura, Ryota Eguchi, Yuichi Sudo, Junya Nakamura, and Yonghwan Kim. Partial Gathering of Mobile Agents in Dynamic Tori. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{shibata_et_al:LIPIcs.SAND.2023.2,
  author =	{Shibata, Masahiro and Kitamura, Naoki and Eguchi, Ryota and Sudo, Yuichi and Nakamura, Junya and Kim, Yonghwan},
  title =	{{Partial Gathering of Mobile Agents in Dynamic Tori}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{2:1--2:22},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.2},
  URN =		{urn:nbn:de:0030-drops-179387},
  doi =		{10.4230/LIPIcs.SAND.2023.2},
  annote =	{Keywords: distributed system, mobile agents, partial gathering, dynamic tori}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.3
Bond Percolation in Small-World Graphs with Power-Law Distribution

Authors: Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi

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

Abstract
Full-bond percolation with parameter p is the process in which, given a graph, for every edge independently, we keep the edge with probability p and delete it with probability 1-p. Bond percolation is studied in parallel computing and network science to understand the resilience of distributed systems to random link failure and the spread of information in networks through unreliable links. Moreover, the full-bond percolation is equivalent to the Reed-Frost process, a network version of SIR epidemic spreading. We consider one-dimensional power-law small-world graphs with parameter α obtained as the union of a cycle with additional long-range random edges: each pair of nodes {u,v} at distance L on the cycle is connected by a long-range edge {u,v}, with probability proportional to 1/L^α. Our analysis determines three phases for the percolation subgraph G_p of the small-world graph, depending on the value of α. - If α < 1, there is a p < 1 such that, with high probability, there are Ω(n) nodes that are reachable in G_p from one another in 𝒪(log n) hops; - If 1 < α < 2, there is a p < 1 such that, with high probability, there are Ω(n) nodes that are reachable in G_p from one another in log^{𝒪(1)}(n) hops; - If α > 2, for every p < 1, with high probability all connected components of G_p have size 𝒪(log n).
Cite as

Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, and Isabella Ziccardi. Bond Percolation in Small-World Graphs with Power-Law Distribution. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{becchetti_et_al:LIPIcs.SAND.2023.3,
  author =	{Becchetti, Luca and Clementi, Andrea and Pasquale, Francesco and Trevisan, Luca and Ziccardi, Isabella},
  title =	{{Bond Percolation in Small-World Graphs with Power-Law Distribution}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{3:1--3:22},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.3},
  URN =		{urn:nbn:de:0030-drops-179392},
  doi =		{10.4230/LIPIcs.SAND.2023.3},
  annote =	{Keywords: Information spreading, gossiping, epidemics, fault-tolerance, network self-organization and formation, complex systems, social and transportation networks}
}
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-dev.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.SAND.2023.5
Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines

Authors: Joshua Ani, Michael Coulombe, Erik D. Demaine, Yevhenii Diomidov, Timothy Gomez, Dylan Hendrickson, and Jayson Lynch

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

Abstract
We extend the motion-planning-through-gadgets framework to several new scenarios involving various numbers of robots/agents, and analyze the complexity of the resulting motion-planning problems. While past work considers just one robot or one robot per player, most of our models allow for one or more locations to spawn new robots in each time step, leading to arbitrarily many robots. In the 0-player context, where all motion is deterministically forced, we prove that deciding whether any robot ever reaches a specified location is undecidable, by representing a counter machine. In the 1-player context, where the player can choose how to move the robots, we prove equivalence to Petri nets, EXPSPACE-completeness for reaching a specified location, PSPACE-completeness for reconfiguration, and ACKERMANN-completeness for reconfiguration when robots can be destroyed in addition to spawned. Finally, we consider a variation on the standard 2-player context where, instead of one robot per player, we have one robot shared by the players, along with a ko rule to prevent immediately undoing the previous move. We prove this impartial 2-player game EXPTIME-complete.
Cite as

Joshua Ani, Michael Coulombe, Erik D. Demaine, Yevhenii Diomidov, Timothy Gomez, Dylan Hendrickson, and Jayson Lynch. Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{ani_et_al:LIPIcs.SAND.2023.5,
  author =	{Ani, Joshua and Coulombe, Michael and Demaine, Erik D. and Diomidov, Yevhenii and Gomez, Timothy and Hendrickson, Dylan and Lynch, Jayson},
  title =	{{Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{5:1--5:21},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.5},
  URN =		{urn:nbn:de:0030-drops-179414},
  doi =		{10.4230/LIPIcs.SAND.2023.5},
  annote =	{Keywords: Gadgets, robots, undecidability, Petri nets}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.6
Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks

Authors: Shunhao Oh, Dana Randall, and Andréa W. Richa

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

Abstract
We develop a framework for self-induced phase changes in programmable matter in which a collection of agents with limited computational and communication capabilities can collectively perform appropriate global tasks in response to local stimuli that dynamically appear and disappear. Agents reside on graph vertices, where each stimulus is only recognized locally, and agents communicate via token passing along edges to alert other agents to transition to an Aware state when stimuli are present and an Unaware state when the stimuli disappear. We present an Adaptive Stimuli Algorithm that is robust to competing waves of messages as multiple stimuli change, possibly adversarially. Moreover, in addition to handling arbitrary stimulus dynamics, the algorithm can handle agents reconfiguring the connections (edges) of the graph over time in a controlled way. As an application, we show how this Adaptive Stimuli Algorithm on reconfigurable graphs can be used to solve the foraging problem, where food sources may be discovered, removed, or shifted at arbitrary times. We would like the agents to consistently self-organize, using only local interactions, such that if the food remains in a position long enough, the agents transition to a gather phase in which many collectively form a single large component with small perimeter around the food. Alternatively, if no food source has existed recently, the agents should undergo a self-induced phase change and switch to a search phase in which they distribute themselves randomly throughout the lattice region to search for food. Unlike previous approaches to foraging, this process is indefinitely repeatable, withstanding competing waves of messages that may interfere with each other. Like a physical phase change, microscopic changes such as the deletion or addition of a single food source trigger these macroscopic, system-wide transitions as agents share information about the environment and respond locally to get the desired collective response.
Cite as

Shunhao Oh, Dana Randall, and Andréa W. Richa. Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.SAND.2023.6,
  author =	{Oh, Shunhao and Randall, Dana and Richa, Andr\'{e}a W.},
  title =	{{Adaptive Collective Responses to Local Stimuli in Anonymous Dynamic Networks}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{6:1--6:23},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.6},
  URN =		{urn:nbn:de:0030-drops-179424},
  doi =		{10.4230/LIPIcs.SAND.2023.6},
  annote =	{Keywords: Dynamic networks, adaptive stimuli, foraging, self-organizing particle systems, programmable matter}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.7
When Should You Wait Before Updating? - Toward a Robustness Refinement

Authors: Swan Dubois, Laurent Feuilloley, Franck Petit, and Mikaël Rabie

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

Abstract
Consider a dynamic network and a given distributed problem. At any point in time, there might exist several solutions that are equally good with respect to the problem specification, but that are different from an algorithmic perspective, because some could be easier to update than others when the network changes. In other words, one would prefer to have a solution that is more robust to topological changes in the network; and in this direction the best scenario would be that the solution remains correct despite the dynamic of the network. In [Arnaud Casteigts et al., 2020], the authors introduced a very strong robustness criterion: they required that for any removal of edges that maintain the network connected, the solution remains valid. They focus on the maximal independent set problem, and their approach consists in characterizing the graphs in which there exists a robust solution (the existential problem), or even stronger, where any solution is robust (the universal problem). As the robustness criteria is very demanding, few graphs have a robust solution, and even fewer are such that all of their solutions are robust. In this paper, we ask the following question: Can we have robustness for a larger class of networks, if we bound the number k of edge removals allowed? To answer this question, we consider three classic problems: maximal independent set, minimal dominating set and maximal matching. For the universal problem, the answers for the three cases are surprisingly different. For minimal dominating set, the class does not depend on the number of edges removed. For maximal matching, removing only one edge defines a robust class related to perfect matchings, but for all other bounds k, the class is the same as for an arbitrary number of edge removals. Finally, for maximal independent set, there is a strict hierarchy of classes: the class for the bound k is strictly larger than the class for bound k+1. For the robustness notion of [Arnaud Casteigts et al., 2020], no characterization of the class for the existential problem is known, only a polynomial-time recognition algorithm. We show that the situation is even worse for bounded k: even for k = 1, it is NP-hard to decide whether a graph has a robust maximal independent set.
Cite as

Swan Dubois, Laurent Feuilloley, Franck Petit, and Mikaël Rabie. When Should You Wait Before Updating? - Toward a Robustness Refinement. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{dubois_et_al:LIPIcs.SAND.2023.7,
  author =	{Dubois, Swan and Feuilloley, Laurent and Petit, Franck and Rabie, Mika\"{e}l},
  title =	{{When Should You Wait Before Updating? - Toward a Robustness Refinement}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{7:1--7:15},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.7},
  URN =		{urn:nbn:de:0030-drops-179435},
  doi =		{10.4230/LIPIcs.SAND.2023.7},
  annote =	{Keywords: Robustness, dynamic network, temporal graphs, edge removal, connectivity, footprint, packing/covering problems, maximal independent set, maximal matching, minimum dominating set, perfect matching, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.8
Dynamic Graphs Generators Analysis: An Illustrative Case Study

Authors: Vincent Bridonneau, Frédéric Guinand, and Yoann Pigné

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

Abstract
In this work, we investigate the analysis of generators for dynamic graphs, which are defined as graphs whose topology changes over time. We focus on generated graphs whose orders are neither growing nor constant along time. We introduce a novel concept, called "sustainability," to qualify the long-term evolution of dynamic graphs. A dynamic graph is considered sustainable if its evolution does not result in a static, empty, or periodic graph. To measure the dynamics of the sets of vertices and edges, we propose a metric, named "Nervousness," which is derived from the Jaccard distance. As an illustration of how the analysis can be conducted, we design a parametrized generator, named D3G3 (Degree-Driven Dynamic Geometric Graphs Generator), that generates dynamic graph instances from an initial geometric graph. The evolution of these instances is driven by two rules that operate on the vertices based on their degree. By varying the parameters of the generator, different properties of the dynamic graphs can be produced. Our results show that in order to ascertain the sustainability of the generated dynamic graphs, it is necessary to study both the evolution of the order and the Nervousness for a given set of parameters.
Cite as

Vincent Bridonneau, Frédéric Guinand, and Yoann Pigné. Dynamic Graphs Generators Analysis: An Illustrative Case Study. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 8:1-8:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bridonneau_et_al:LIPIcs.SAND.2023.8,
  author =	{Bridonneau, Vincent and Guinand, Fr\'{e}d\'{e}ric and Pign\'{e}, Yoann},
  title =	{{Dynamic Graphs Generators Analysis: An Illustrative Case Study}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{8:1--8:19},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.8},
  URN =		{urn:nbn:de:0030-drops-179443},
  doi =		{10.4230/LIPIcs.SAND.2023.8},
  annote =	{Keywords: Dynamic Graphs, Graph Generation, Graph Properties, Evolutionary models}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.9
Complexity of the Temporal Shortest Path Interdiction Problem

Authors: Jan Boeckmann, Clemens Thielen, and Alina Wittmann

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

Abstract
In the shortest path interdiction problem, an interdictor aims to remove arcs of total cost at most a given budget from a directed graph with given arc costs and traversal times such that the length of a shortest s-t-path is maximized. For static graphs, this problem is known to be strongly NP-hard, and it has received considerable attention in the literature. While the shortest path problem is one of the most fundamental and well-studied problems also for temporal graphs, the shortest path interdiction problem has not yet been formally studied on temporal graphs, where common definitions of a "shortest path" include: latest start path (path with maximum start time), earliest arrival path (path with minimum arrival time), shortest duration path (path with minimum traveling time including waiting times at nodes), and shortest traversal path (path with minimum traveling time not including waiting times at nodes). In this paper, we analyze the complexity of the shortest path interdiction problem on temporal graphs with respect to all four definitions of a shortest path mentioned above. Even though the shortest path interdiction problem on static graphs is known to be strongly NP-hard, we show that the latest start and the earliest arrival path interdiction problems on temporal graphs are polynomial-time solvable. For the shortest duration and shortest traversal path interdiction problems, however, we show strong NP-hardness, but we obtain polynomial-time algorithms for these problems on extension-parallel temporal graphs.
Cite as

Jan Boeckmann, Clemens Thielen, and Alina Wittmann. Complexity of the Temporal Shortest Path Interdiction Problem. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{boeckmann_et_al:LIPIcs.SAND.2023.9,
  author =	{Boeckmann, Jan and Thielen, Clemens and Wittmann, Alina},
  title =	{{Complexity of the Temporal Shortest Path Interdiction Problem}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{9:1--9:20},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.9},
  URN =		{urn:nbn:de:0030-drops-179455},
  doi =		{10.4230/LIPIcs.SAND.2023.9},
  annote =	{Keywords: Temporal Graphs, Interdiction Problems, Complexity, Shortest Paths, Most Vital Arcs}
}
Document
DOI: 10.4230/LIPIcs.SAND.2023.10
A Connectivity-Sensitive Approach to Consensus Dynamics

Authors: Bernard Chazelle and Kritkorn Karntikoon

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

Abstract
The paper resolves a long-standing open question in network dynamics. Averaging-based consensus has long been known to exhibit an exponential gap in relaxation time between the connected and disconnected cases, but a satisfactory explanation has remained elusive. We provide one by deriving nearly tight bounds on the s-energy of disconnected systems. This in turn allows us to relate the convergence rate of consensus dynamics to the number of connected components. We apply our results to opinion formation in social networks and provide a theoretical validation of the concept of an Overton window as an attracting manifold of "viable" opinions.
Cite as

Bernard Chazelle and Kritkorn Karntikoon. A Connectivity-Sensitive Approach to Consensus Dynamics. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chazelle_et_al:LIPIcs.SAND.2023.10,
  author =	{Chazelle, Bernard and Karntikoon, Kritkorn},
  title =	{{A Connectivity-Sensitive Approach to Consensus Dynamics}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{10:1--10:17},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.10},
  URN =		{urn:nbn:de:0030-drops-179464},
  doi =		{10.4230/LIPIcs.SAND.2023.10},
  annote =	{Keywords: s-energy, dynamic networks, relaxation time, multiagent systems}
}
  • Refine by Author
  • 18 Spirakis, Paul G.
  • 8 Mertzios, George B.
  • 8 Spirakis, Paul
  • 5 Deligkas, Argyrios
  • 4 Zamaraev, Viktor
  • Show More...

  • Refine by Classification
  • 14 Mathematics of computing → Graph algorithms
  • 11 Mathematics of computing → Graph theory
  • 11 Theory of computation → Graph algorithms analysis
  • 8 Theory of computation → Distributed algorithms
  • 8 Theory of computation → Problems, reductions and completeness
  • Show More...

  • Refine by Keyword
  • 3 Kolmogorov complexity
  • 3 Temporal graph
  • 3 complexity
  • 2 Algorithms
  • 2 Approximation Algorithms
  • Show More...

  • Refine by Type
  • 125 document
  • 2 volume

  • Refine by Publication Year
  • 90 2018
  • 19 2023
  • 3 2017
  • 3 2020
  • 3 2022
  • Show More...

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