11 Search Results for "Opatrny, Jaroslav"

Document
DOI: 10.4230/LIPIcs.FUN.2026.10
77 Shades of Grey

Authors: Quentin Bramas, Stéphane Devismes, Anaïs Durand, Pascal Lafourcade, and Anissa Lamani

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
Bruce Wayne contacted us to help him develop a new surveillance technology for dark environments such as caves, using a swarm of Unmanned Aerial Vehicles (UAVs), called Batdroids. A Batdroid has no chirality, limited visibility, and a perfect clock to synchronize with the others. A Batdroid can produce 77 shades of grey in dark mode and four colors in light mode. In this paper, we propose two algorithms using three Batdroids to perpetually explore a finite 3D grid modeling a cave. The first algorithm operates in darkness, uses 77 shades of grey, and requires visibility range one. The second operates in light, uses four colors and visibility range two. We also prove that three is the optimal number of Batdroids required to solve Bruce Wayne’s challenge.
Cite as

Quentin Bramas, Stéphane Devismes, Anaïs Durand, Pascal Lafourcade, and Anissa Lamani. 77 Shades of Grey. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.FUN.2026.10,
  author =	{Bramas, Quentin and Devismes, St\'{e}phane and Durand, Ana\"{i}s and Lafourcade, Pascal and Lamani, Anissa},
  title =	{{77 Shades of Grey}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.10},
  URN =		{urn:nbn:de:0030-drops-257294},
  doi =		{10.4230/LIPIcs.FUN.2026.10},
  annote =	{Keywords: Mobile robots, grid exploration, perpetual exploration}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.4
Visualization of Event Graphs for Train Schedules

Authors: Johann Hartleb, Marie Schmidt, Samuel Wolf, and Alexander Wolff

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
Train timetables can be represented as event graphs, where events correspond to a train passing through a location at a certain point in time. A visual representation of an event graph is important for many applications such as dispatching and (the development of) dispatching software. A common way to represent event graphs are time-space diagrams. In such a diagram, key locations are visualized on the y-axis and time on the x-axis of a coordinate system. A train’s movement is then represented as a connected sequence of line segments in this coordinate system. This visualization allows for an easy detection of infrastructure conflicts and safety distance violations. However, time-space diagrams are usually used only to depict event graphs that are restricted to corridors, where an obvious ordering of the locations exists. In this paper, we consider the visualization of general event graphs in time-space diagrams, where the challenge is to find an ordering of the locations that produces readable drawings. We argue that this means to minimize the number of turns, i.e., the total number of changes in y-direction. To this end, we establish a connection between this problem and Maximum Betweenness. Then we develop a preprocessing strategy to reduce the instance size. We also propose a parameterized algorithm and integer linear programming formulations. We experimentally evaluate the preprocessing strategy and the integer programming formulations on a real-world dataset. Our best algorithm solves every instance in the dataset in less than a second. This suggests that turn-optimal time-space diagrams can be computed in real time.
Cite as

Johann Hartleb, Marie Schmidt, Samuel Wolf, and Alexander Wolff. Visualization of Event Graphs for Train Schedules. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hartleb_et_al:OASIcs.ATMOS.2025.4,
  author =	{Hartleb, Johann and Schmidt, Marie and Wolf, Samuel and Wolff, Alexander},
  title =	{{Visualization of Event Graphs for Train Schedules}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{4:1--4:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.4},
  URN =		{urn:nbn:de:0030-drops-247607},
  doi =		{10.4230/OASIcs.ATMOS.2025.4},
  annote =	{Keywords: Graph Drawing, Event Graphs, Integer Linear Programming, Parameterized Algorithms, Treewidth}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.83
Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction

Authors: Michael Pinsker, Jakub Rydval, Moritz Schöbi, and Christoph Spiess

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
The Feder-Vardi dichotomy conjecture for Constraint Satisfaction Problems (CSPs) with finite templates, confirmed independently by Bulatov and Zhuk, has an extension to certain well-behaved infinite templates due to Bodirsky and Pinsker which remains wide open. We provide answers to three fundamental questions on the scope of the Bodirsky-Pinsker conjecture. Our first two main results provide two simplifications of this scope, one of structural, and the other one of algebraic nature. The former simplification implies that the conjecture is equivalent to its restriction to templates without algebraicity, a crucial assumption in the most powerful classification methods. The latter yields that the higher-arity invariants of any template within its scope can be assumed to be essentially injective, and any algebraic condition characterizing any complexity class within the conjecture closed under Datalog reductions must be satisfiable by injections, thus lifting the mystery of the better applicability of certain conditions over others. Our third main result uses the first one to show that any non-trivially tractable template within the scope serves, up to a Datalog-computable modification of it, as the witness of the tractability of a non-finitely tractable finite-domain Promise Constraint Satisfaction Problem (PCSP) by the so-called sandwich method. This generalizes a recent result of Mottet and provides a strong hitherto unknown connection between the Bodirsky-Pinsker conjecture and finite-domain PCSPs.
Cite as

Michael Pinsker, Jakub Rydval, Moritz Schöbi, and Christoph Spiess. Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 83:1-83:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pinsker_et_al:LIPIcs.MFCS.2025.83,
  author =	{Pinsker, Michael and Rydval, Jakub and Sch\"{o}bi, Moritz and Spiess, Christoph},
  title =	{{Three Fundamental Questions in Modern Infinite-Domain Constraint Satisfaction}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{83:1--83:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.83},
  URN =		{urn:nbn:de:0030-drops-241903},
  doi =		{10.4230/LIPIcs.MFCS.2025.83},
  annote =	{Keywords: (Promise) Constraint Satisfaction Problem, dichotomy conjecture, polymorphism, identity, algebraicity, homogeneity, \omega-categoricity, finite boundedness, Datalog}
}
Document
DOI: 10.4230/OASIcs.Manzini.12
Wheeler Graphs and Wheeler Languages

Authors: Nicola Cotumaccio, Giovanna D'Agostino, Daniel Gibney, Alberto Policriti, Nicola Prezza, and Sharma V. Thankachan

Published in: OASIcs, Volume 131, The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday (2025)

Abstract
Suffix sorting stands at the core of the most efficient solutions for indexed pattern matching: the suffix tree, the suffix array, compressed indexes based on the Burrows-Wheeler transform, and so on. In [Gagie, Manzini, Sirén, TCS 2017] this concept was extended to labeled graphs, obtaining the rich class of Wheeler graphs. This work opened a very fruitful line of research, ultimately generating results able to bridge the fields of compressed data structures, graph theory, and regular language theory. In a Wheeler graph, nodes are sorted according to the alphabetic order of their incoming labels, propagating this order through pairs of equally-labeled edges. This apparently-simple definition makes it possible to solve on Wheeler graphs problems (including, but not limited to: compression, subpath queries, NFA equivalence, determinization, minimization) that on general labeled graphs are extremely hard to solve, and induces a rich structure in the class of regular languages (Wheeler languages) recognized by automata whose state transition is a Wheeler graph. The goal of this survey is to provide a summary of (and intuitions behind) the results on Wheeler graphs that appeared in the literature since their introduction, in addition to a discussion of interesting problems that are still open in the field.
Cite as

Nicola Cotumaccio, Giovanna D'Agostino, Daniel Gibney, Alberto Policriti, Nicola Prezza, and Sharma V. Thankachan. Wheeler Graphs and Wheeler Languages. In The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday. Open Access Series in Informatics (OASIcs), Volume 131, pp. 12:1-12:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cotumaccio_et_al:OASIcs.Manzini.12,
  author =	{Cotumaccio, Nicola and D'Agostino, Giovanna and Gibney, Daniel and Policriti, Alberto and Prezza, Nicola and Thankachan, Sharma V.},
  title =	{{Wheeler Graphs and Wheeler Languages}},
  booktitle =	{The Expanding World of Compressed Data: A Festschrift for Giovanni Manzini's 60th Birthday},
  pages =	{12:1--12:28},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-390-4},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{131},
  editor =	{Ferragina, Paolo and Gagie, Travis and Navarro, Gonzalo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.Manzini.12},
  URN =		{urn:nbn:de:0030-drops-239205},
  doi =		{10.4230/OASIcs.Manzini.12},
  annote =	{Keywords: Wheeler languages, Wheeler graphs, pattern matching, indexing, compressed data structures}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.9
Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents

Authors: Quentin Bramas, Toshimitsu Masuzawa, and Sébastien Tixeuil

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
We consider the problem of graph exploration by energy sharing mobile agents that are subject to crash faults. More precisely, we consider a team of two agents where at most one of them may fail unpredictably, and the considered topology is that of connected acyclic graphs (i.e. trees). We consider both the asynchronous and the synchronous settings, and we provide necessary and sufficient conditions about the energy.
Cite as

Quentin Bramas, Toshimitsu Masuzawa, and Sébastien Tixeuil. Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bramas_et_al:LIPIcs.OPODIS.2024.9,
  author =	{Bramas, Quentin and Masuzawa, Toshimitsu and Tixeuil, S\'{e}bastien},
  title =	{{Crash-Tolerant Exploration of Trees by Energy-Sharing Mobile Agents}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.9},
  URN =		{urn:nbn:de:0030-drops-225452},
  doi =		{10.4230/LIPIcs.OPODIS.2024.9},
  annote =	{Keywords: Mobile Agents, Distributed Algorithms, Energy sharing}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.57
Group Evacuation on a Line by Agents with Different Communication Abilities

Authors: Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, and Sunil Shende

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We consider evacuation of a group of n ≥ 2 autonomous mobile agents (or robots) from an unknown exit on an infinite line. The agents are initially placed at the origin of the line and can move with any speed up to the maximum speed 1 in any direction they wish and they all can communicate when they are co-located. However, the agents have different wireless communication abilities: while some are fully wireless and can send and receive messages at any distance, a subset of the agents are senders, they can only transmit messages wirelessly, and the rest are receivers, they can only receive messages wirelessly. The agents start at the same time and their communication abilities are known to each other from the start. Starting at the origin of the line, the goal of the agents is to collectively find a target/exit at an unknown location on the line while minimizing the evacuation time, defined as the time when the last agent reaches the target. We investigate the impact of such a mixed communication model on evacuation time on an infinite line for a group of cooperating agents. In particular, we provide evacuation algorithms and analyze the resulting competitive ratio (CR) of the evacuation time for such a group of agents. If the group has two agents of two different types, we give an optimal evacuation algorithm with competitive ratio CR = 3+2√2. If there is a single sender or fully wireless agent, and multiple receivers we prove that CR ∈ [2+√5,5], and if there are multiple senders and a single receiver or fully wireless agent, we show that CR ∈ [3,5.681319]. Any group consisting of only senders or only receivers requires competitive ratio 9, and any other combination of agents has competitive ratio 3.
Cite as

Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, and Sunil Shende. Group Evacuation on a Line by Agents with Different Communication Abilities. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 57:1-57:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{czyzowicz_et_al:LIPIcs.ISAAC.2021.57,
  author =	{Czyzowicz, Jurek and Killick, Ryan and Kranakis, Evangelos and Krizanc, Danny and Narayanan, Lata and Opatrny, Jaroslav and Pankratov, Denis and Shende, Sunil},
  title =	{{Group Evacuation on a Line by Agents with Different Communication Abilities}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{57:1--57:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.57},
  URN =		{urn:nbn:de:0030-drops-154903},
  doi =		{10.4230/LIPIcs.ISAAC.2021.57},
  annote =	{Keywords: Agent, Communication, Evacuation, Mobile, Receiver, Search, Sender}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.137
Energy Consumption of Group Search on a Line

Authors: Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende

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

Abstract
Consider two robots that start at the origin of the infinite line in search of an exit at an unknown location on the line. The robots can collaborate in the search, but can only communicate if they arrive at the same location at exactly the same time, i.e. they use the so-called face-to-face communication model. The group search time is defined as the worst-case time as a function of d, the distance of the exit from the origin, when both robots can reach the exit. It has long been known that for a single robot traveling at unit speed, the search time is at least 9d - o(d); a simple doubling strategy achieves this time bound. It was shown recently in [Chrobak et al., 2015] that k >= 2 robots traveling at unit speed also require at least 9d group search time. We investigate energy-time trade-offs in group search by two robots, where the energy loss experienced by a robot traveling a distance x at constant speed s is given by s^2 x, as motivated by energy consumption models in physics and engineering. Specifically, we consider the problem of minimizing the total energy used by the robots, under the constraints that the search time is at most a multiple c of the distance d and the speed of the robots is bounded by b. Motivation for this study is that for the case when robots must complete the search in 9d time with maximum speed one (b=1; c=9), a single robot requires at least 9d energy, while for two robots, all previously proposed algorithms consume at least 28d/3 energy. When the robots have bounded memory and can use only a constant number of fixed speeds, we generalize an algorithm described in [Baeza-Yates and Schott, 1995; Chrobak et al., 2015] to obtain a family of algorithms parametrized by pairs of b,c values that can solve the problem for the entire spectrum of these pairs for which the problem is solvable. In particular, for each such pair, we determine optimal (and in some cases nearly optimal) algorithms inducing the lowest possible energy consumption. We also propose a novel search algorithm that simultaneously achieves search time 9d and consumes energy 8.42588d. Our result shows that two robots can search on the line in optimal time 9d while consuming less total energy than a single robot within the same search time. Our algorithm uses robots that have unbounded memory, and a finite number of dynamically computed speeds. It can be generalized for any c, b with cb=9, and consumes energy 8.42588b^2d.
Cite as

Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende. Energy Consumption of Group Search on a Line. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 137:1-137:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{czyzowicz_et_al:LIPIcs.ICALP.2019.137,
  author =	{Czyzowicz, Jurek and Georgiou, Konstantinos and Killick, Ryan and Kranakis, Evangelos and Krizanc, Danny and Lafond, Manuel and Narayanan, Lata and Opatrny, Jaroslav and Shende, Sunil},
  title =	{{Energy Consumption of Group Search on a Line}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{137:1--137: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.137},
  URN =		{urn:nbn:de:0030-drops-107138},
  doi =		{10.4230/LIPIcs.ICALP.2019.137},
  annote =	{Keywords: Evacuation, Exit, Line, Face-to-face Communication, Robots, Search}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.139
Exploration of High-Dimensional Grids by Finite Automata

Authors: Stefan Dobrev, Lata Narayanan, Jaroslav Opatrny, and Denis Pankratov

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

Abstract
We consider the problem of finding a treasure at an unknown point of an n-dimensional infinite grid, n >= 3, by initially collocated finite automaton agents (scouts/robots). Recently, the problem has been well characterized for 2 dimensions for deterministic as well as randomized agents, both in synchronous and semi-synchronous models [S. Brandt et al., 2018; Y. Emek et al., 2015]. It has been conjectured that n+1 randomized agents are necessary to solve this problem in the n-dimensional grid [L. Cohen et al., 2017]. In this paper we disprove the conjecture in a strong sense: we show that three randomized synchronous agents suffice to explore an n-dimensional grid for any n. Our algorithm is optimal in terms of the number of the agents. Our key insight is that a constant number of finite automaton agents can, by their positions and movements, implement a stack, which can store the path being explored. We also show how to implement our algorithm using: four randomized semi-synchronous agents; four deterministic synchronous agents; or five deterministic semi-synchronous agents. We give a different algorithm that uses 4 deterministic semi-synchronous agents for the 3-dimensional grid. This is provably optimal, and surprisingly, matches the result for 2 dimensions. For n >= 4, the time complexity of the solutions mentioned above is exponential in distance D of the treasure from the starting point of the agents. We show that in the deterministic case, one additional agent brings the time down to a polynomial. Finally, we focus on algorithms that never venture much beyond the distance D. We describe an algorithm that uses O(sqrt{n}) semi-synchronous deterministic agents that never go beyond 2D, as well as show that any algorithm using 3 synchronous deterministic agents in 3 dimensions, if it exists, must travel beyond Omega(D^{3/2}) from the origin.
Cite as

Stefan Dobrev, Lata Narayanan, Jaroslav Opatrny, and Denis Pankratov. Exploration of High-Dimensional Grids by Finite Automata. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 139:1-139:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{dobrev_et_al:LIPIcs.ICALP.2019.139,
  author =	{Dobrev, Stefan and Narayanan, Lata and Opatrny, Jaroslav and Pankratov, Denis},
  title =	{{Exploration of High-Dimensional Grids by Finite Automata}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{139:1--139:16},
  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.139},
  URN =		{urn:nbn:de:0030-drops-107153},
  doi =		{10.4230/LIPIcs.ICALP.2019.139},
  annote =	{Keywords: Multi-agent systems, finite state machines, high-dimensional grids, robot exploration, randomized agents, semi-synchronous and synchronous agents}
}
Document
DOI: 10.4230/LIPIcs.FUN.2018.16
God Save the Queen

Authors: Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende

Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)

Abstract
Queen Daniela of Sardinia is asleep at the center of a round room at the top of the tower in her castle. She is accompanied by her faithful servant, Eva. Suddenly, they are awakened by cries of "Fire". The room is pitch black and they are disoriented. There is exactly one exit from the room somewhere along its boundary. They must find it as quickly as possible in order to save the life of the queen. It is known that with two people searching while moving at maximum speed 1 anywhere in the room, the room can be evacuated (i.e., with both people exiting) in 1 + (2 pi)/3 + sqrt{3} ~~ 4.8264 time units and this is optimal [Czyzowicz et al., DISC'14], assuming that the first person to find the exit can directly guide the other person to the exit using her voice. Somewhat surprisingly, in this paper we show that if the goal is to save the queen (possibly leaving Eva behind to die in the fire) there is a slightly better strategy. We prove that this "priority" version of evacuation can be solved in time at most 4.81854. Furthermore, we show that any strategy for saving the queen requires time at least 3 + pi/6 + sqrt{3}/2 ~~ 4.3896 in the worst case. If one or both of the queen's other servants (Biddy and/or Lili) are with her, we show that the time bounds can be improved to 3.8327 for two servants, and 3.3738 for three servants. Finally we show lower bounds for these cases of 3.6307 (two servants) and 3.2017 (three servants). The case of n >= 4 is the subject of an independent study by Queen Daniela's Royal Scientific Team.
Cite as

Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende. God Save the Queen. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 16:1-16:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{czyzowicz_et_al:LIPIcs.FUN.2018.16,
  author =	{Czyzowicz, Jurek and Georgiou, Konstantinos and Killick, Ryan and Kranakis, Evangelos and Krizanc, Danny and Narayanan, Lata and Opatrny, Jaroslav and Shende, Sunil},
  title =	{{God Save the Queen}},
  booktitle =	{9th International Conference on Fun with Algorithms (FUN 2018)},
  pages =	{16:1--16:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-067-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{100},
  editor =	{Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.16},
  URN =		{urn:nbn:de:0030-drops-88074},
  doi =		{10.4230/LIPIcs.FUN.2018.16},
  annote =	{Keywords: Algorithm, Evacuation, Exit, Disk, Wireless Communication, Queen, Priority, Robots, Search, Servants, Trajectory}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.11
Evacuating an Equilateral Triangle in the Face-to-Face Model

Authors: Huda Chuangpishit, Saeed Mehrabi, Lata Narayanan, and Jaroslav Opatrny

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
Consider k robots initially located at the centroid of an equilateral triangle T of sides of length one. The goal of the robots is to evacuate T through an exit at an unknown location on the boundary of T. Each robot can move anywhere in T independently of other robots with maximum speed one. The objective is to minimize the evacuation time, which is defined as the time required for all k robots to reach the exit. We consider the face-to-face communication model for the robots: a robot can communicate with another robot only when they meet in T. In this paper, we give upper and lower bounds for the face-to-face evacuation time by k robots. We show that for any k, any algorithm for evacuating k >= 1 robots from T requires at least sqrt(3) time. This bound is asymptotically optimal, as we show that a straightforward strategy of evacuation by k robots gives an upper bound of sqrt(3) + 3/k. For k = 3, 4, 5, 6, we show significant improvements on the obvious upper bound by giving algorithms with evacuation times of 2.0887, 1.9816, 1.876, and 1.827, respectively. For k = 2 robots, we give a lower bound of 1 + 2/sqrt(3) ~= 2.154, and an algorithm with upper bound of 2.3367 on the evacuation time.
Cite as

Huda Chuangpishit, Saeed Mehrabi, Lata Narayanan, and Jaroslav Opatrny. Evacuating an Equilateral Triangle in the Face-to-Face Model. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chuangpishit_et_al:LIPIcs.OPODIS.2017.11,
  author =	{Chuangpishit, Huda and Mehrabi, Saeed and Narayanan, Lata and Opatrny, Jaroslav},
  title =	{{Evacuating an Equilateral Triangle in the Face-to-Face Model}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.11},
  URN =		{urn:nbn:de:0030-drops-86310},
  doi =		{10.4230/LIPIcs.OPODIS.2017.11},
  annote =	{Keywords: Distributed algorithms, Robots evacuation, Face-to-face communication, Equilateral triangle}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.27
Search on a Line by Byzantine Robots

Authors: Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We consider the problem of fault-tolerant parallel search on an infinite line by n robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed 1 and can communicate in wireless mode among themselves. However, among the n robots, there are f robots that exhibit byzantine faults. A faulty robot can fail to report the target even after reaching it, or it can make malicious claims about having found the target when in fact it has not. Given the presence of such faulty robots, the search for the target can only be concluded when the non-faulty robots have sufficient verification that the target has been found. We aim to design algorithms that minimize the value of S_d (n, f), the time to find a target at a distance d from the origin by n robots among which f are faulty. We give several different algorithms whose running time depends on the ratio f/n, the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots.
Cite as

Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende. Search on a Line by Byzantine Robots. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 27:1-27:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{czyzowicz_et_al:LIPIcs.ISAAC.2016.27,
  author =	{Czyzowicz, Jurek and Georgiou, Konstantinos and Kranakis, Evangelos and Krizanc, Danny and Narayanan, Lata and Opatrny, Jaroslav and Shende, Sunil},
  title =	{{Search on a Line by Byzantine Robots}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{27:1--27:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.27},
  URN =		{urn:nbn:de:0030-drops-67972},
  doi =		{10.4230/LIPIcs.ISAAC.2016.27},
  annote =	{Keywords: Cow path problem, Parallel search, Mobile robots, Wireless communication, Byzantine faults}
}
  • Refine by Type
  • 11 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 4 2025
  • 1 2021
  • 2 2019
  • 2 2018
  • Show More...

  • Refine by Author
  • 6 Narayanan, Lata
  • 6 Opatrny, Jaroslav
  • 4 Czyzowicz, Jurek
  • 4 Kranakis, Evangelos
  • 4 Krizanc, Danny
  • Show More...

  • Refine by Series/Journal
  • 9 LIPIcs
  • 2 OASIcs

  • Refine by Classification
  • 3 Computing methodologies → Mobile agents
  • 2 Theory of computation → Distributed algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Computing methodologies → Distributed artificial intelligence
  • 1 Theory of computation
  • Show More...

  • Refine by Keyword
  • 3 Evacuation
  • 3 Search
  • 2 Exit
  • 2 Mobile robots
  • 2 Robots
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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