References
389 entries. Keys are used as [Key] citations throughout the catalogue.
Shannon1951Maze
Claude E. Shannon (1951). Presentation of a maze-solving machine. Transactions of the 8th Conference on Cybernetics (Macy Conference), pp. 173–180.
No DOI; citation details as given by Disser et al. 2019. The link is a popular account of the machine (Theseus, first prototype 1950), not the paper.
Bellman1963Optimal
Richard Bellman (1963). An Optimal Search. SIAM Review 5(3):274.
Problem statement posing linear search. Metadata from Crossref; not read, cited as reported by Czyzowicz2021Byzantine and Brandt2020Rays.
Beck1964Linear
Anatole Beck (1964). On the linear search problem. Israel Journal of Mathematics 2(4):221–228.
Blum1978Compass
Manuel Blum, Dexter Kozen (1978). On the power of the compass (or, why mazes are easier to search than graphs). FOCS 1978, pp. 132–142.
Checked against the full text: two pebbles, or two cooperating automata, search every maze; no three automata search all finite cubic embedded graphs (Theorem 6.1).
Budach1978Labyrinths
Lothar Budach (1978). Automata and labyrinths. Mathematische Nachrichten 86:195–282.
Original not read; the statement used here is as cited by Disser et al. 2019.
Aleliunas1979Random
Romas Aleliunas, Richard M. Karp, Richard J. Lipton, László Lovász, Charles Rackoff (1979). Random walks, universal traversal sequences, and the complexity of maze problems. FOCS 1979, pp. 218–223.
doi:10.1109/SFCS.1979.34
cited in randomized
Rollik1980Planar
Hans-Anton Rollik (1980). Automaten in planaren Graphen. Acta Informatica 13(3):287–298.
Original not read; statements used here are as cited by Disser et al. 2019 and Czyzowicz et al. 2012.
Dudek1991Robotic
G. Dudek, M. Jenkin, E. Milios, D. Wilkes (1991). Robotic exploration as graph construction. IEEE Transactions on Robotics and Automation 7(6):859–865.
doi:10.1109/70.105395
cited in marker
Toffoli1991Programmable
Tommaso Toffoli, Norman Margolus (1991). Programmable matter: Concepts and realization. Physica D: Nonlinear Phenomena 47(1–2):263–272.
Coined the term programmable matter. Metadata from Crossref; not read, cited as reported by DiLuna2020Shape, Emek2019Deterministic and Dufoulon2021Efficient.
BaezaYates1993Searching
Ricardo A. Baeza-Yates, Joseph C. Culberson, Gregory J. E. Rawlins (1993). Searching in the Plane. Information and Computation 106(2):234–252.
doi:10.1006/inco.1993.1054
cited in line, rays
Kao1996Randomized
Ming-Yang Kao, John H. Reif, Stephen R. Tate (1996). Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem. Information and Computation 131(1):63–79 (SODA 1993).
Priezzhev1996Eulerian
V. B. Priezzhev, Deepak Dhar, Abhishek Dhar, Supriya Krishnamurthy (1996). Eulerian Walkers as a Model of Self-Organized Criticality. Physical Review Letters 77(25):5079–5082.
Metadata from Crossref. Not read; cited as the origin of the rotor-router by Takahashi et al. 2026 and Hiraoka et al. 2026.
Flocchini1998Direction
Paola Flocchini, Bernard Mans, Nicola Santoro (1998). Sense of direction: Definitions, properties, and classes. Networks 32(3):165–180.
Metadata from Crossref. Not read; cited by Dobrev et al. 2006 as the source of the formal definition of sense of direction, which is used in the black hole search knowledge axis.
Ando1999Convergence
Hideki Ando, Yoshinobu Oasa, Ichiro Suzuki, Masafumi Yamashita (1999). Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Transactions on Robotics and Automation 15(5):818–828.
doi:10.1109/70.795787
cited in limited-ssync
Deng1999Exploring
Xiaotie Deng, Christos H. Papadimitriou (1999). Exploring an unknown graph. Journal of Graph Theory 32(3):265–297 (FOCS 1990).
Flocchini1999Hard
Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Peter Widmayer (1999). Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots. ISAAC 1999, LNCS 1741, pp. 93–102.
Checked against the full text: introduces the asynchronous (CORDA) model and studies pattern formation without common handedness.
Suzuki1999Formation
Ichiro Suzuki, Masafumi Yamashita (1999). Distributed anonymous mobile robots: formation of geometric patterns. SIAM Journal on Computing 28(4):1347–1363.
Albers2000Exploring
Susanne Albers, Monika R. Henzinger (2000). Exploring unknown environments. SIAM Journal on Computing 29(4):1164–1188.
Barriere2002Capture
Lali Barrière, Paola Flocchini, Pierre Fraigniaud, Nicola Santoro (2002). Capture of an intruder by mobile agents. SPAA 2002, pp. 200–209.
doi:10.1145/564870.564906
cited in trees
Bender2002Pebble
Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil Vadhan (2002). The power of a pebble: exploring and mapping directed graphs. Information and Computation 176(1):1–21 (STOC 1998).
DOI from Crossref; bounds read in the journal manuscript. STOC 1998 version: doi 10.1145/276698.276759.
Defago2002Circle
Xavier Défago, Akihiko Konagaya (2002). Circle formation for oblivious anonymous mobile robots with no common sense of orientation. POMC 2002, pp. 97–104.
doi:10.1145/584490.584509
cited in ssync
Diks2004Tree
Krzysztof Diks, Pierre Fraigniaud, Evangelos Kranakis, Andrzej Pelc (2002). Tree exploration with little memory. SODA 2002, pp. 588–597; journal version: Journal of Algorithms 51(1):38–63, 2004.
link
cited in trees-perpetual, trees-stop, trees-return
Koucky2002Backtracking
Michal Koucký (2002). Universal traversal sequences with backtracking. Journal of Computer and System Sciences 65(4):717–726 (CCC 2001).
Yanovski2003Ant
Vladimir Yanovski, Israel A. Wagner, Alfred M. Bruckstein (2003). A distributed ant algorithm for efficiently patrolling a network. Algorithmica 37(3):165–186.
Metadata from Crossref. Full text not read (no open copy found); bounds taken from the abstract and from Menc et al. 2017.
Dumitrescu2004Metamorphic
Adrian Dumitrescu, Ichiro Suzuki, Masafumi Yamashita (2004). Motion Planning for Metamorphic Systems: Feasibility, Decidability, and Distributed Reconfiguration. IEEE Transactions on Robotics and Automation 20(3):409–418.
Metamorphic systems with rotation and sliding moves; cited by Michail2019Transformation as the closest prior work. Metadata from Crossref; not read.
Fraigniaud2004Digraphs
Pierre Fraigniaud, David Ilcinkas (2004). Digraphs exploration with little memory. STACS 2004, pp. 246–257.
Gervasi2004Flocking
Vincenzo Gervasi, Giuseppe Prencipe (2004). Coordination without communication: the case of the flocking problem. Discrete Applied Mathematics 144(3):324–344.
doi:10.1016/j.dam.2003.11.010
cited in basic
Cohen2005Gravitational
Reuven Cohen, David Peleg (2005). Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM Journal on Computing 34(6):1516–1528 (ESA 2004).
doi:10.1137/S0097539704446475
cited in async
Fleischer2005Exploring
Rudolf Fleischer, Gerhard Trippen (2005). Exploring an unknown graph efficiently. ESA 2005, pp. 11–22.
doi:10.1007/11561071_4
cited in directed-labelled
Flocchini2005Limited
Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Peter Widmayer (2005). Gathering of asynchronous robots with limited visibility. Theoretical Computer Science 337(1–3):147–168 (STACS 2001).
Fraigniaud2005Automaton
Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, David Peleg (2005). Graph exploration by a finite automaton. Theoretical Computer Science 345(2–3):331–344 (MFCS 2004).
Fraigniaud2005Space
Pierre Fraigniaud, David Ilcinkas, Sergio Rajsbaum, Sébastien Tixeuil (2005). Space Lower Bounds for Graph Exploration via Reduced Automata. SIROCCO 2005, LNCS 3499, pp. 140–154.
doi:10.1007/11429647_13
cited in one-pebble
Peleg2005Swarms
David Peleg (2005). Distributed Coordination Algorithms for Mobile Robot Swarms: New Directions and Challenges. IWDC 2005, LNCS 3741, pp. 1–12.
Checked against the full text: suggests "colors, flags or visible indicator lights" and \(O(1)\) bits of stable memory for robots.
Agmon2006Fault
Noa Agmon, David Peleg (2006). Fault-Tolerant Gathering Algorithms for Autonomous Mobile Robots. SIAM Journal on Computing 36(1):56–82.
doi:10.1137/050645221
cited in crash, byzantine-ssync, byzantine-fsync
Czyzowicz2006Complexity
Jurek Czyzowicz, Dariusz Kowalski, Euripides Markou, Andrzej Pelc (2006). Complexity of Searching for a Black Hole. Fundamenta Informaticae 71(2–3):229–242.
doi:10.3233/FUN-2006-712-305
cited in sync-map
Defago2006Fault
Xavier Défago, Maria Gradinariu, Stéphane Messika, Philippe Raipin-Parvédy (2006). Fault-Tolerant and Self-stabilizing Mobile Robots Gathering. DISC 2006, LNCS, pp. 46–60.
Metadata from Crossref. Abstract read (Semantic Scholar): deterministic and probabilistic gathering under crash and Byzantine faults and bounded schedulers.
DeMarco2006Asynchronous
Gianluca De Marco, Luisa Gargano, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Ugo Vaccaro (2006). Asynchronous deterministic rendezvous in graphs. Theoretical Computer Science 355(3):315–326 (MFCS 2005).
doi:10.1016/j.tcs.2005.12.016
cited in async
Dessmark2006Deterministic
Anders Dessmark, Pierre Fraigniaud, Dariusz R. Kowalski, Andrzej Pelc (2006). Deterministic rendezvous in graphs. Algorithmica 46(1):69–96 (ESA 2003, without Kowalski).
Dobrev2006Searching
Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro (2006). Searching for a black hole in arbitrary networks: optimal mobile agents protocols. Distributed Computing 19(1) (PODC 2002).
Fraigniaud2006Collective
Pierre Fraigniaud, Leszek Gąsieniec, Dariusz R. Kowalski, Andrzej Pelc (2006). Collective tree exploration. Networks 48(3):166–177 (LATIN 2004).
Fraigniaud2006Oracle
Pierre Fraigniaud, David Ilcinkas, Andrzej Pelc (2006). Oracle size: a new measure of difficulty for communication tasks. PODC 2006, pp. 179–187.
Metadata from Crossref. Not read; cited by Cohen et al. 2008 among works on short information supplied in advance (the advice paradigm).
Fraigniaud2006Reduced
Pierre Fraigniaud, David Ilcinkas, Sergio Rajsbaum, Sébastien Tixeuil (2006). The reduced automata technique for graph exploration space lower bounds. Theoretical Computer Science: Essays in Memory of Shimon Even, LNCS, pp. 1–26 (SIROCCO 2005).
Das2007Map
Shantanu Das, Paola Flocchini, Shay Kutten, Amiya Nayak, Nicola Santoro (2007). Map construction of unknown graphs by multiple agents. Theoretical Computer Science 385(1–3):34–48.
doi:10.1016/j.tcs.2007.05.011
cited in team
Dobrev2007Ring
Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro (2007). Mobile Search for a Black Hole in an Anonymous Ring. Algorithmica 48(1):67–90 (DISC 2001).
doi:10.1007/s00453-006-1232-z
cited in async-ring
Dynia2007Maps
Mirosław Dynia, Jakub Łopuszański, Christian Schindelhauer (2007). Why robots need maps. SIROCCO 2007, pp. 41–50.
Efrima2007Models
Asaf Efrima, David Peleg (2007). Distributed Models and Algorithms for Mobile Robot Systems. SOFSEM 2007, LNCS 4362, pp. 70–87.
Metadata from Crossref. Not read; cited with Peleg 2005 for the lights suggestion, as reported by Das et al. 2016.
Klasing2007Hardness
Ralf Klasing, Euripides Markou, Tomasz Radzik, Fabiano Sarracco (2007). Hardness and approximation results for Black Hole Search in arbitrary networks. Theoretical Computer Science 384(2–3):201–221 (SIROCCO 2005).
doi:10.1016/j.tcs.2007.04.024
cited in sync-map
Prencipe2007Impossibility
Giuseppe Prencipe (2007). Impossibility of gathering by a set of autonomous mobile robots. Theoretical Computer Science 384(2–3):222–231 (SIROCCO 2005).
The conference version (SIROCCO 2005) was read; the journal version was not.
Xin2007Faster
Qin Xin (2007). Faster treasure hunt and better strongly universal exploration sequences. ISAAC 2007, pp. 549–560.
Blin2008Chasing
Lélia Blin, Pierre Fraigniaud, Nicolas Nisse, Sandrine Vial (2008). Distributed chasing of network intruders. Theoretical Computer Science 399(1–2):12–37 (SIROCCO 2006).
Metadata from Crossref (SIROCCO 2006 version: doi 10.1007/11780823_7). Not read; its result (one searcher above optimum, non-monotone, unknown graphs) is as reported by Ilcinkas et al. 2009.
Cohen2008Label
Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman, David Peleg (2008). Label-guided graph exploration by a finite automaton. ACM Transactions on Algorithms 4(4) (ICALP 2005).
Cohen2008Spreading
Reuven Cohen, David Peleg (2008). Local spreading algorithms for autonomous robot systems. Theoretical Computer Science 399(1–2):71–82 (SIROCCO 2006).
Defago2008NonUniform
Xavier Défago, Samia Souissi (2008). Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity. Theoretical Computer Science 396(1–3):97–112.
doi:10.1016/j.tcs.2008.01.050
cited in ssync
Dieudonne2008Circle
Yoann Dieudonné, Ouiddad Labbani-Igbida, Franck Petit (2008). Circle formation of weak mobile robots. ACM Transactions on Autonomous and Adaptive Systems 3(4), article 16 (SSS 2006).
Flocchini2008Arbitrary
Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Peter Widmayer (2008). Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theoretical Computer Science 407(1–3):412–447.
Flocchini2008Deployment
Paola Flocchini, Giuseppe Prencipe, Nicola Santoro (2008). Self-deployment of mobile sensors on a ring. Theoretical Computer Science 402(1):67–80 (ALGOSENSORS 2006).
doi:10.1016/j.tcs.2008.03.006
cited in oriented
Flocchini2008Hypercubes
Paola Flocchini, Miao Jun Huang, Flaminia L. Luccio (2008). Decontamination of hypercubes by mobile agents. Networks 52(3):167–178 (IPDPS 2005).
doi:10.1002/net.20240
cited in hypercube
Fraigniaud2008Advice
Pierre Fraigniaud, David Ilcinkas, Andrzej Pelc (2008). Tree exploration with advice. Information and Computation 206(11):1276–1287 (MFCS 2006, as "Tree Exploration with an Oracle").
Metadata from Crossref (MFCS 2006 version: doi 10.1007/11821069_2). Not read; cited by Miller & Pelc 2015 as earlier work on advice for mobile agents.
Gasieniec2008Periodic
Leszek Gąsieniec, Ralf Klasing, Russell Martin, Alfredo Navarra, Xiaohui Zhang (2008). Fast periodic graph exploration with constant memory. Journal of Computer and System Sciences 74(5).
Conference version at SIROCCO 2007.
Ilcinkas2008Ports
David Ilcinkas (2008). Setting port numbers for fast graph exploration. Theoretical Computer Science 401:236–242 (SIROCCO 2006).
Klasing2008Ring
Ralf Klasing, Euripides Markou, Andrzej Pelc (2008). Gathering asynchronous oblivious mobile robots in a ring. Theoretical Computer Science 390(1):27–39 (ISAAC 2006).
Kowalski2008Meet
Dariusz R. Kowalski, Adam Malinowski (2008). How to meet in anonymous network. Theoretical Computer Science 399(1–2):141–156 (SIROCCO 2006).
doi:10.1016/j.tcs.2008.02.010
cited in labelled
Bounds cited as reported by Pelc 2019.
Reingold2008Undirected
Omer Reingold (2008). Undirected connectivity in log-space. Journal of the ACM 55(4), article 17 (STOC 2005).
doi:10.1145/1391289.1391291
cited in known-n
Bampas2009LockIn
Evangelos Bampas, Leszek Gąsieniec, Nicolas Hanusse, David Ilcinkas, Ralf Klasing, Adrian Kosowski (2009). Euler Tour Lock-In Problem in the Rotor-Router Model. DISC 2009, LNCS, pp. 423–435.
Metadata from Crossref. Full text not read (HAL unavailable when checked); the authors' DISC 2009 slides and the HAL abstract were read.
Czyzowicz2009Fat
Jurek Czyzowicz, Leszek Gąsieniec, Andrzej Pelc (2009). Gathering few fat mobile robots in the plane. Theoretical Computer Science 410(6–7):481–499 (OPODIS 2006).
doi:10.1016/j.tcs.2008.10.005
cited in fat-few
Dieudonne2009Scatter
Yoann Dieudonné, Franck Petit (2009). Scatter of robots. Parallel Processing Letters 19(1):175–184.
Efrima2009Partition
Asaf Efrima, David Peleg (2009). Distributed algorithms for partitioning a swarm of autonomous mobile robots. Theoretical Computer Science 410(14):1355–1368 (SIROCCO 2007).
Ilcinkas2009Monotonicity
David Ilcinkas, Nicolas Nisse, David Soguet (2009). The cost of monotonicity in distributed graph searching. Distributed Computing 22(2):117–127 (OPODIS 2007).
Chalopin2010Map
Jérémie Chalopin, Shantanu Das, Adrian Kosowski (2010). Constructing a Map of an Anonymous Graph: Applications of Universal Sequences. OPODIS 2010, pp. 119–134.
doi:10.1007/978-3-642-17653-1_10
cited in single
Clement2010Cost
Julien Clement, Xavier Défago, Maria Gradinariu Potop-Butucaru, Taisuke Izumi, Stephane Messika (2010). The cost of probabilistic agreement in oblivious robot networks. Information Processing Letters 110(11):431–438.
Dieudonne2010Leader
Yoann Dieudonné, Franck Petit, Vincent Villain (2010). Leader election problem versus pattern formation problem. DISC 2010, pp. 267–281.
Fekete2010Rectilinear
Sándor Fekete, Chris Gray, Alexander Kröller (2010). Evacuation of Rectilinear Polygons. Combinatorial Optimization and Applications, pp. 21-30.
GanChaudhuri2010Transparent
Sruti Gan Chaudhuri, Krishnendu Mukhopadhyaya (2010). Gathering Asynchronous Transparent Fat Robots. ICDCIT 2010, LNCS 5966, pp. 170–175.
Kuhn2010Dynamic
Fabian Kuhn, Nancy Lynch, Rotem Oshman (2010). Distributed computation in dynamic networks. STOC 2010, pp. 513–522.
Introduces T-interval connectivity (T = 1: connected in every round); token-circulation impossibility in 1-interval connected graphs. Metadata from Crossref; abstract and introduction read in the authors' full version (papers/Kuhn2010Dynamic.pdf).
Lamani2010Ring
Anissa Lamani, Maria Gradinariu Potop-Butucaru, Sébastien Tixeuil (2010). Optimal Deterministic Ring Exploration with Oblivious Asynchronous Robots. SIROCCO 2010.
Ambuhl2011Tree
Christoph Ambühl, Leszek Gąsieniec, Andrzej Pelc, Tomasz Radzik, Xiaohui Zhang (2011). Tree exploration with logarithmic memory. ACM Transactions on Algorithms 7(2), article 17 (SODA 2007).
Bandettini2011Survey
Alberto Bandettini, Fabio Luporini, Giovanni Viglietta (2011). A Survey on Open Problems for Mobile Robots. arXiv preprint.
Metadata from arXiv. Read (Sections 1–2): survey of the CORDA/ATOM models, multiplicity detection, limited visibility and fat robots. Preprint, not peer reviewed.
Bouzid2011Homonyms
Zohir Bouzid, Anissa Lamani (2011). Robot Networks with Homonyms: The Case of Patterns Formation. SSS 2011, pp. 92–107.
CordLandwehr2011Convergence
Andreas Cord-Landwehr, Bastian Degener, Matthias Fischer, Martina Hüllmann, Barbara Kempkes, Alexander Klaas, Peter Kling, Sven Kurras, Marcus Märtens, Friedhelm Meyer auf der Heide, Christoph Raupach, Kamil Swierkot, Daniel Warner, Christoph Weddemann, Daniel Wonisch (2011). A new approach for analyzing convergence algorithms for mobile robots. ICALP 2011, pp. 650–661.
Czyzowicz2011Patrolling
Jurek Czyzowicz, Leszek Gąsieniec, Adrian Kosowski, Evangelos Kranakis (2011). Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds. ESA 2011, pp. 701–712.
doi:10.1007/978-3-642-23719-5_59
cited in segment
Degener2011Tight
Bastian Degener, Barbara Kempkes, Tobias Langner, Friedhelm Meyer auf der Heide, Peter Pietrzyk, Roger Wattenhofer (2011). A tight runtime bound for synchronous gathering of autonomous robots with limited visibility. SPAA 2011, pp. 139–148.
doi:10.1145/1989493.1989515
cited in limited-fsync
Abstract not fully read; the bound is as restated by Castenow et al. 2022.
Guilbault2011Asynchronous
Samuel Guilbault, Andrzej Pelc (2011). Asynchronous rendezvous of anonymous agents in arbitrary graphs. OPODIS 2011, pp. 421–434.
Katreniak2011Convergence
Branislav Katreniak (2011). Convergence with limited visibility by asynchronous mobile robots. SIROCCO 2011, pp. 125–137.
Abstract seen only as a search snippet; the result is confirmed by Kirkpatrick et al. 2024.
Casteigts2012TVG
Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro (2012). Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems 27(5):387–408 (ADHOC-NOW 2011).
Unified TVG framework and hierarchy of classes (Class 5 recurrent connectivity, Class 9 always connected, Class 10 T-interval connectivity). Metadata from Crossref; introduction and Section 5 read in the arXiv version.
Cieliebak2012Gathering
Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro (2012). Distributed Computing by Mobile Robots: Gathering. SIAM Journal on Computing 41(4):829–879 (ICALP 2003).
doi:10.1137/100796534
cited in async-weak
Czyzowicz2012Everywhere
Jurek Czyzowicz, Andrzej Pelc, Arnaud Labourel (2012). How to meet asynchronously (almost) everywhere. ACM Transactions on Algorithms 8(4), article 37 (SODA 2010).
doi:10.1145/2344422.2344427
cited in async
Czyzowicz2012Forget
Jurek Czyzowicz, Adrian Kosowski, Andrzej Pelc (2012). How to meet when you forget: log-space rendezvous in arbitrary graphs. Distributed Computing 25(2):165–178 (PODC 2010).
doi:10.1007/s00446-011-0141-9
cited in anonymous
Czyzowicz2012Periodic
Jurek Czyzowicz, Stefan Dobrev, Leszek Gąsieniec, David Ilcinkas, Jesper Jansson, Ralf Klasing, Ioannis Lignos, Russell Martin, Kunihiko Sadakane, Wing-Kin Sung (2012). More efficient periodic traversal in anonymous undirected graphs. Theoretical Computer Science 444:60–76 (SIROCCO 2009).
Devismes2012Grid
Stéphane Devismes, Anissa Lamani, Franck Petit, Pascal Raymond, Sébastien Tixeuil (2012). Optimal Grid Exploration by Asynchronous Oblivious Robots. SSS 2012, pp. 64–76; journal: The Computer Journal 64(1):132–154.
Dieudonne2012Tokens
Yoann Dieudonné, Andrzej Pelc (2012). Deterministic network exploration by a single agent with Byzantine tokens. Information Processing Letters 112:467–470.
Flocchini2012Book
Paola Flocchini, Giuseppe Prencipe, Nicola Santoro (2012). Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool.
Metadata from Crossref. Only the abstract was read (via Semantic Scholar); used for the 'minimal capabilities' framing of the field.
Flocchini2012PingPong
Paola Flocchini, David Ilcinkas, Nicola Santoro (2012). Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pebbles. Algorithmica 62(3–4):1006–1033 (DISC 2008).
doi:10.1007/s00453-011-9496-3
cited in tokens-map
Izumi2012TwoRobots
Taisuke Izumi, Samia Souissi, Yoshiaki Katayama, Nobuhiro Inuzuka, Xavier Défago, Koichi Wada, Masafumi Yamashita (2012). The gathering problem for two oblivious robots with unreliable compasses. SIAM Journal on Computing 41(1):26–46.
Kosowski2012Decomposition
Adrian Kosowski, Alfredo Navarra (2012). Graph decomposition for memoryless periodic exploration. Algorithmica 63(1–2):26–38 (MFCS 2009).
Zhang2012Ratio
Meng Zhang, Yi Zhang, Jijun Tang (2012). Label-Guided Graph Exploration with Adjustable Ratio of Labels. arXiv preprint 1204.2955.
Metadata from arXiv. Abstract read.
Agathangelou2013Fat
Chrysovalandis Agathangelou, Chryssis Georgiou, Marios Mavronicolas (2013). A distributed algorithm for gathering many fat mobile robots in the plane. PODC 2013, pp. 250–259.
Bouzid2013Crash
Zohir Bouzid, Shantanu Das, Sebastien Tixeuil (2013). Gathering of Mobile Robots Tolerating Multiple Crash Faults. ICDCS 2013, pp. 337–346.
Datta2013Local
Ajoy K. Datta, Anissa Lamani, Lawrence L. Larmore, Franck Petit (2013). Ring exploration by oblivious agents with local vision. ICDCS 2013, pp. 347–356.
doi:10.1109/ICDCS.2013.55arXiv:1205.5003
cited in ring-fsync-stop, ring-oblivious-fsync-stop, ring-oblivious-async-stop
Metadata from Crossref. Checked against the arXiv version (“Ring Exploration with Oblivious Myopic Robots”, May 2012, which treats \(\varphi = 1, 2, 3\)): contribution, Theorems 3.1–3.2, Corollary 3.2 and the synchronous algorithms of Section 3.2. The \(\varphi = 2, 3\) results also appeared as an SSS 2013 brief announcement (doi 10.1007/978-3-319-03089-0_31), not read.
Delporte2013Homonyms
Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Anne-Marie Kermarrec, Eric Ruppert, Hung Tran-The (2013). Byzantine agreement with homonyms. Distributed Computing 26(5–6):321–340 (PODC 2011).
Metadata from Crossref; conference version PODC 2011, pp. 21–30, doi:10.1145/1993806.1993810. Not read; cited as the origin of the homonymous model, as reported by Bouzid & Lamani 2011.
Dieudonne2013Geoleader
Yoann Dieudonné, Florence Levé, Franck Petit, Vincent Villain (2013). Deterministic geoleader election in disoriented anonymous systems. Theoretical Computer Science 506:43–54.
Dobrev2013Tokens
Stefan Dobrev, Paola Flocchini, Rastislav Královič, Nicola Santoro (2013). Exploring an unknown dangerous graph using tokens. Theoretical Computer Science 472:28–45.
doi:10.1016/j.tcs.2012.11.022
cited in tokens
Flocchini2013Ring
Paola Flocchini, David Ilcinkas, Andrzej Pelc, Nicola Santoro (2013). Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots. Algorithmica 65(3):562–583 (OPODIS 2007).
doi:10.1007/s00453-011-9611-5
cited in ring
Fraigniaud2013Delays
Pierre Fraigniaud, Andrzej Pelc (2013). Delays induce an exponential memory gap for rendezvous in trees. ACM Transactions on Algorithms 9(2), article 17 (DISC 2008).
Viglietta2013Rendezvous
Giovanni Viglietta (2013). Rendezvous of Two Robots with Visible Bits. ALGOSENSORS 2013, pp. 291–306.
Xu2013Groups
Yinfeng Xu, Lan Qin (2013). Strategies of Groups Evacuation from a Convex Region in the Plane. Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, pp. 250-260.
Czyzowicz2014Evacuating
Jurek Czyzowicz, Leszek Gąsieniec, Thomas Gorry, Evangelos Kranakis, Russell Martin, Dominik Pajak (2014). Evacuating Robots via Unknown Exit in a Disk. DISC 2014, pp. 122–136.
Derakhshandeh2014Amoebot
Zahra Derakhshandeh, Shlomi Dolev, Robert Gmyr, Andréa W. Richa, Christian Scheideler, Thim Strothmann (2014). Amoebot - a new model for programmable matter. SPAA 2014 brief announcement, pp. 220–222.
Dieudonne2014Mischief
Yoann Dieudonné, Andrzej Pelc, David Peleg (2014). Gathering Despite Mischief. ACM Transactions on Algorithms 11(1) (SODA 2012).
doi:10.1145/2629656
cited in weak-byzantine, byzantine
DiLuna2014Robots
Giuseppe Antonio Di Luna, Paola Flocchini, Sruti Gan Chaudhuri, Nicola Santoro, Giovanni Viglietta (2014). Robots with Lights: Overcoming Obstructed Visibility Without Colliding. SSS 2014, LNCS 8756, pp. 150–164.
Higashikawa2014Online
Yuya Higashikawa, Naoki Katoh, Stefan Langerman, Shin-ichi Tanigawa (2014). Online graph exploration algorithms for cycles and trees by multiple searchers. Journal of Combinatorial Optimization 28(2):480–495.
TaShma2014Deterministic
Amnon Ta-Shma, Uri Zwick (2014). Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. ACM Transactions on Algorithms 10(3), article 12 (SODA 2007).
doi:10.1145/2601068
cited in finite, labelled
Wei2014Convex
Qi Wei, Xuehou Tan, Bo Jiang, Lijuan Wang (2014). On-Line Strategies for Evacuating from a Convex Region in the Plane. Combinatorial Optimization and Applications, pp. 74-85.
Different authors from Li & Xu 2017, which has a similar title.
Yamauchi2014Randomized
Yukiko Yamauchi, Masafumi Yamashita (2014). Randomized Pattern Formation Algorithm for Asynchronous Oblivious Mobile Robots. DISC 2014, LNCS, pp. 137–151.
Metadata from Crossref. Not read; result as reported by Bramas & Tixeuil 2016.
Bramas2015WaitFree
Quentin Bramas, Sébastien Tixeuil (2015). Wait-Free Gathering Without Chirality. SIROCCO 2015, pp. 313–327.
doi:10.1007/978-3-319-25258-2_22
cited in crash
Chrobak2015GroupSearch
Marek Chrobak, Leszek Gąsieniec, Thomas Gorry, Russell Martin (2015). Group Search on the Line. SOFSEM 2015, LNCS, pp. 164–176.
Czyzowicz2015Wireless
J. Czyzowicz, E. Kranakis, D. Krizanc, L. Narayanan, J. Opatrny, S. Shende (2015). Wireless Autonomous Robot Evacuation from Equilateral Triangles and Squares. ADHOC-NOW 2015, LNCS, pp. 181–194.
Das2015Sequences
Shantanu Das, Paola Flocchini, Nicola Santoro, Masafumi Yamashita (2015). Forming sequences of geometric patterns with oblivious mobile robots. Distributed Computing 28(2):131–145 (PODC 2010).
Derakhshandeh2015Leader
Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida Bazzi, Andréa W. Richa, Christian Scheideler (2015). Leader Election and Shape Formation with Self-organizing Programmable Matter. DNA 21 (2015), pp. 117–132.
Dereniowski2015Fast
Dariusz Dereniowski, Yann Disser, Adrian Kosowski, Dominik Pająk, Przemysław Uznański (2015). Fast collaborative graph exploration. Information and Computation 243:37–49 (ICALP 2013).
Dieudonne2015Polynomial
Yoann Dieudonné, Andrzej Pelc, Vincent Villain (2015). How to meet asynchronously at polynomial cost. SIAM Journal on Computing 44(3):844–867 (PODC 2013).
doi:10.1137/130931990
cited in async
Fujinaga2015Pattern
Nao Fujinaga, Yukiko Yamauchi, Hirotaka Ono, Shuji Kijima, Masafumi Yamashita (2015). Pattern formation by oblivious asynchronous mobile robots. SIAM Journal on Computing 44(3):740–785 (DISC 2012).
doi:10.1137/140958682
cited in chirality
GanChaudhuri2015Leader
Sruti Gan Chaudhuri, Krishnendu Mukhopadhyaya (2015). Leader election and gathering for asynchronous fat robots without common chirality. Journal of Discrete Algorithms 33:171–192.
Jiang2015Groups
Bo Jiang, Yuan Liu, Hao Zhang, Xuehou Tan (2015). An On-Line Strategy of Groups Evacuation from a Convex Region in the Plane. Mathematical Problems in Data Science, pp. 189-199.
Kawamura2015Fence
Akitoshi Kawamura, Yusuke Kobayashi (2015). Fence patrolling by mobile agents with distinct speeds. Distributed Computing 28:147–154 (ISAAC 2012).
Liu2015Groups
Yuan Liu, Bo Jiang, Hao Zhang (2015). Online Strategies for Evacuating from a Convex Region by Groups in the Plane. 2015 Ninth International Conference on Frontier of Computer Science and Technology, pp. 178-183.
Miller2015Tradeoffs
Avery Miller, Andrzej Pelc (2015). Tradeoffs between cost and information for rendezvous and treasure hunt. Journal of Parallel and Distributed Computing 83:159–167 (OPODIS 2014).
Pagli2015Near
Linda Pagli, Giuseppe Prencipe, Giovanni Viglietta (2015). Getting close without touching: near-gathering for autonomous mobile robots. Distributed Computing 28(5):333–349 (SIROCCO 2012).
Sharma2015Optimal
Gokarna Sharma, Costas Busch, Supratik Mukhopadhyay (2015). Mutual Visibility with an Optimal Number of Colors. ALGOSENSORS 2015, pp. 196–210.
Sudo2015Whiteboards
Yuichi Sudo, Daisuke Baba, Junya Nakamura, Fukuhito Ooshita, Hirotsugu Kakugawa, Toshimitsu Masuzawa (2015). A Single Agent Exploration in Unknown Undirected Graphs with Whiteboards. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E98.A(10):2117–2128.
Metadata from Crossref. Not read; described in Takahashi et al. 2026.
Vaidyanathan2015Log
Ramachandran Vaidyanathan, Costas Busch, Jerry L. Trahan, Gokarna Sharma, Suresh Rai (2015). Logarithmic-Time Complete Visibility for Robots with Lights. IPDPS 2015, pp. 375–384.
Balamohan2016Tokens
B. Balamohan, S. Dobrev, P. Flocchini, N. Santoro (2016). Exploring an unknown dangerous graph with a constant number of tokens. Theoretical Computer Science 610:169–181 (SIROCCO 2012).
doi:10.1016/j.tcs.2014.07.013
cited in tokens
Bouchard2016Byzantine
Sébastien Bouchard, Yoann Dieudonné, Bertrand Ducourthial (2016). Byzantine gathering in networks. Distributed Computing 29(6):435–457 (SIROCCO 2015).
doi:10.1007/s00446-016-0276-9
cited in byzantine
Bramas2016Probabilistic
Quentin Bramas, Sébastien Tixeuil (2016). Probabilistic asynchronous arbitrary pattern formation. SSS 2016, pp. 88–93 (brief announcement at PODC 2016).
Cannon2016Compression
Sarah Cannon, Joshua J. Daymude, Dana Randall, Andréa W. Richa (2016). A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems. PODC 2016, pp. 279–288.
Czyzowicz2016MultipleExits
Jurek Czyzowicz, Stefan Dobrev, Konstantinos Georgiou, Evangelos Kranakis, Fraser MacQuarrie (2016). Evacuating two robots from multiple unknown exits in a circle. ICDCN 2016.
Journal version: Theoretical Computer Science 709:20–30 (2018), doi:10.1016/j.tcs.2016.11.019.
Czyzowicz2019FaultyLine
Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny (2016). Search on a Line with Faulty Robots. PODC 2016, pp. 405–414; journal: Distributed Computing 32(6):493–504 (2019).
doi:10.1145/2933057.2933102
cited in line-crash
Das2016Lights
Shantanu Das, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Masafumi Yamashita (2016). Autonomous mobile robots with lights. Theoretical Computer Science 609:171–184 (ICDCS 2012).
doi:10.1016/j.tcs.2015.09.018
cited in two-lights
Derakhshandeh2016Universal
Zahra Derakhshandeh, Robert Gmyr, Andrea W. Richa, Christian Scheideler, Thim Strothmann (2016). Universal Shape Formation for Programmable Matter. SPAA 2016, pp. 289–299.
doi:10.1145/2935764.2935784
cited in universal
Dieudonne2016Anonymous
Yoann Dieudonné, Andrzej Pelc (2016). Anonymous Meeting in Networks. Algorithmica 74(2):908–946 (SODA 2013).
doi:10.1007/s00453-015-9982-0
cited in anonymous
Flocchini2016Constant
Paola Flocchini, Nicola Santoro, Giovanni Viglietta, Masafumi Yamashita (2016). Rendezvous with constant memory. Theoretical Computer Science 621:57–72 (SIROCCO 2013).
Mamino2016Square
Marcello Mamino, Giovanni Viglietta (2016). Square formation by asynchronous oblivious robots. CCCG 2016.
arXiv:1605.06093
cited in async
Venue as cited by Flocchini et al. 2017; no DOI.
Michail2016Temporal
Othon Michail, Paul G. Spirakis (2016). Traveling salesman problems in temporal graphs. Theoretical Computer Science 634:1–23.
Metadata from Crossref; conference version not checked. Not read; credited by Erlebach et al. 2021 with introducing temporal graph exploration (TEXP) with the schedule known in advance.
Sharma2016Complete
Gokarna Sharma, Ramachandran Vaidyanathan, Jerry L. Trahan, Costas Busch, Suresh Rai (2016). Complete Visibility for Robots with Lights in O(1) Time. SSS 2016, LNCS 10083, pp. 327–345.
doi:10.1007/978-3-319-49259-9_26
cited in lights
Wei2016Affected
Qi Wei, Xuehou Tan, Bo Jiang, Lijuan Wang (2016). Evacuating from an Unknown Affected Area. International Journal of Pattern Recognition and Artificial Intelligence 30, pp. 1659022.
Wei2016Competitive
Qi WEI, Xuehou TAN, Bo JIANG (2016). Competitive Strategies for Evacuating from an Unknown Affected Area. IEICE Transactions on Information and Systems E99.D(10):2585–2590.
Bramas2017RandomBit
Quentin Bramas, Sébastien Tixeuil (2017). The Random Bit Complexity of Mobile Robots Scattering. International Journal of Foundations of Computer Science 28(2):111–133 (ADHOC-NOW 2015).
Brandt2017Collaboration
Sebastian Brandt, Felix Laufenberg, Yuezhou Lv, David Stolz, Roger Wattenhofer (2017). Collaboration Without Communication: Evacuating Two Robots from a Disk. CIAC 2017, pp. 104–115.
Czyzowicz2017Faulty
Jurek Czyzowicz, Konstantinos Georgiou, Maxime Godon, Evangelos Kranakis, Danny Krizanc, Wojciech Rytter, Michał Włodarczyk (2017). Evacuation from a Disc in the Presence of a Faulty Robot. SIROCCO 2017, pp. 158–173.
Czyzowicz2017Patrolmen
Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Evangelos Kranakis, Danny Krizanc, Najmeh Taleb (2017). When Patrolmen Become Corrupted: Monitoring a Graph Using Faulty Mobile Robots. Algorithmica 79(3):925–940 (ISAAC 2015).
Daymude2017Improved
Joshua J. Daymude, Robert Gmyr, Andréa W. Richa, Christian Scheideler, Thim Strothmann (2017). Improved Leader Election for Self-organizing Programmable Matter. ALGOSENSORS 2017, pp. 127–140.
Derakhshandeh2017Coating
Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, Thim Strothmann (2017). Universal coating for programmable matter. Theoretical Computer Science 671:56–68.
DiLuna2017Mutual
Giuseppe A. Di Luna, Paola Flocchini, Sruti Gan Chaudhuri, Federico Poloni, Nicola Santoro, Giovanni Viglietta (2017). Mutual visibility by luminous robots without collisions. Information and Computation 254:392–418.
Flocchini2017Uniform
Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Giovanni Viglietta (2017). Distributed computing by mobile robots: uniform circle formation. Distributed Computing 30(6):413–457 (OPODIS 2014).
Li2017Convex
Songhua Li, Yinfeng Xu (2017). Online Strategies for Evacuating from a Convex Region in the Plane. Frontiers in Algorithmics, pp. 151-162.
Different authors from Wei et al. 2014, which has a similar title.
Menc2017Rotor
Artur Menc, Dominik Pająk, Przemysław Uznański (2017). Time and space optimality of rotor-router graph exploration. Information Processing Letters 127:17–20.
Metadata from Crossref. Checked against the full text (arXiv v3): Observation 1.1, Theorems 2.2 and 2.3.
Mondal2017Uniform
Moumita Mondal, Sruti Gan Chaudhuri (2017). Uniform Circle Formation by Transparent Fat Robots. arXiv preprint.
arXiv:1710.09423
cited in fat-ssync
Preprint, not peer reviewed.
Okumura2017Rendezvous
Takashi Okumura, Koichi Wada, Yoshiaki Katayama (2017). Brief Announcement: Optimal Asynchronous Rendezvous for Mobile Robots with Lights. SSS 2017 (brief announcement), LNCS, pp. 484–488.
Sharma2017Logarithmic
Gokarna Sharma, Ramachandran Vaidyanathan, Jerry L. Trahan, Costas Busch, Suresh Rai (2017). O(log N)-Time Complete Visibility for Asynchronous Robots with Lights. IPDPS 2017, pp. 513–522.
Agarwalla2018DynamicRings
Ankush Agarwalla, John Augustine, William K. Moses Jr., Madhav Sankar K., Arvind Krishna Sridhar (2018). Deterministic Dispersion of Mobile Robots in Dynamic Rings. ICDCN 2018.
Aljohani2018Faults
Aisha Aljohani, Gokarna Sharma (2018). Complete Visibility for Mobile Robots with Lights Tolerating Faults. International Journal of Networking and Computing 8(1):32–52.
doi:10.15803/ijnc.8.1_32
cited in crash, byzantine
AndresArroyo2018Bridging
Marta Andrés Arroyo, Sarah Cannon, Joshua J. Daymude, Dana Randall, Andréa W. Richa (2018). A stochastic approach to shortcut bridging in programmable matter. Natural Computing 17:723–741.
Augustine2018Tradeoffs
John Augustine, William K. Moses Jr. (2018). Dispersion of Mobile Robots: A Study of Memory-Time Trade-offs. ICDCN 2018.
doi:10.1145/3154273.3154293arXiv:1707.05629
cited in anonymous-n-agents, base, rooted, async, ring, tree, tree-rooted, crash, byzantine, byzantine-ring, byzantine-grid
Introduces the problem. All bounds are for \(k = n\); agents know \(n\) and \(m\).
Bramas2018Four
Quentin Bramas, Sébastien Tixeuil (2018). Arbitrary pattern formation with four robots. SSS 2018, pp. 333–348.
Czyzowicz2018GodSaveQueen
Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Sunil Shende (2018). God Save the Queen. FUN 2018, LIPIcs 100, 16:1–16:20.
Journal version: Theoretical Computer Science 806:595–616 (2020), doi:10.1016/j.tcs.2019.09.026.
Czyzowicz2018Priority
Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Sunil Shende (2018). Priority Evacuation from a Disk Using Mobile Robots. SIROCCO 2018, pp. 392–407.
Daymude2018Coating
Joshua J. Daymude, Zahra Derakhshandeh, Robert Gmyr, Alexandra Porter, Andréa W. Richa, Christian Scheideler, Thim Strothmann (2018). On the runtime of universal coating for programmable matter. Natural Computing 17:81–96 (DNA 22, 2016).
Feletti2018Opaque
Caterina Feletti, Carlo Mereghetti, Beatrice Palano (2018). Uniform circle formation for swarms of opaque robots with lights. SSS 2018, pp. 317–332.
Abstract not read; result as reported by Feletti et al. 2024.
Heriban2018Optimally
Adam Heriban, Xavier Défago, Sébastien Tixeuil (2018). Optimally Gathering Two Robots. ICDCN 2018, pp. 1–10.
Ilcinkas2018Ring
David Ilcinkas, Ahmed Mouhamadou Wade (2018). Exploration of the T-interval-connected dynamic graphs: the case of the ring. Theory of Computing Systems 62(5):1144–1160 (SIROCCO 2013).
Izumi2018Connectivity
Taisuke Izumi, Daichi Kaino, Maria Gradinariu Potop-Butucaru, Sébastien Tixeuil (2018). On time complexity for connectivity-preserving scattering of mobile robots. Theoretical Computer Science 738:42–52 (SSS 2010).
doi:10.1016/j.tcs.2018.04.047
cited in limited
Kupavskii2018Lower
Andrey Kupavskii, Emo Welzl (2018). Lower bounds for searching robots, some faulty. PODC 2018.
arXiv:1707.05077
cited in line-crash, line-byzantine, line-crash
Venue from the arXiv comment; DOI not checked.
Liu2018Team
Zhiqiang Liu, Yukiko Yamauchi, Shuji Kijima, Masafumi Yamashita (2018). Team assembling problem for asynchronous heterogeneous mobile robots. Theoretical Computer Science 721:27–41.
Pattanayak2018TwoExits
Debasish Pattanayak, H. Ramesh, Partha Sarathi Mandal, Stefan Schmid (2018). Evacuating Two Robots from Two Unknown Exits on the Perimeter of a Disk with Wireless Communication. ICDCN 2018 (short paper).
Pelc2018Crash
Andrzej Pelc (2018). Deterministic gathering with crash faults. Networks 72(2):182–199.
Gathering with motion and total crash faults; impossibility under full asynchrony (3-node clique argument), solved with fixed speeds. Metadata from Crossref; abstract and introduction read in the arXiv version.
Sharma2018Fat
Gokarna Sharma, Rusul Alsaedi, Costas Busch, Supratik Mukhopadhyay (2018). The Complete Visibility Problem for Fat Robots with Lights. ICDCN 2018.
doi:10.1145/3154273.3154319
cited in fat-fsync
Bagheri2019Triangles
Iman Bagheri, Lata Narayanan, Jaroslav Opatrny (2019). Evacuation of Equilateral Triangles by Mobile Agents of Limited Communication Range. ALGOSENSORS 2019, LNCS, pp. 3–22.
Bampas2019Speeds
Evangelos Bampas, Jurek Czyzowicz, Leszek Gąsieniec, David Ilcinkas, Ralf Klasing, Tomasz Kociumaka, Dominik Pająk (2019). Linear Search by a Pair of Distinct-Speed Robots. Algorithmica 81(1):317–342 (SIROCCO 2016).
Bazzi2019Stationary
Rida A. Bazzi, Joseph L. Briones (2019). Stationary and Deterministic Leader Election in Self-organizing Particle Systems. SSS 2019, LNCS, pp. 22–37.
Brief announcement at SSS 2018.
Cannon2019Separation
Sarah Cannon, Joshua J. Daymude, Cem Gökmen, Dana Randall, Andréa W. Richa (2019). A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems. APPROX/RANDOM 2019, LIPIcs 145, 54:1–54:22.
Chuangpishit2019Average
Huda Chuangpishit, Konstantinos Georgiou, Preeti Sharma (2019). Average Case - Worst Case Tradeoffs for Evacuating 2 Robots from the Disk in the Face-to-Face Model. ALGOSENSORS 2018, LNCS.
Cicerone2019Asynchronous
Serafino Cicerone, Gabriele Di Stefano, Alfredo Navarra (2019). Asynchronous arbitrary pattern formation: the effects of a rigorous approach. Distributed Computing 32(2):91–132.
Czyzowicz2019Energy
Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny, Sunil Shende (2019). Energy Consumption of Group Search on a Line. ICALP 2019, LIPIcs 132, 137:1–137:15.
Czyzowicz2019GroupSearch
Jurek Czyzowicz, Kostantinos Georgiou, Evangelos Kranakis (2019). Group Search and Evacuation. Lecture Notes in Computer Science Distributed Computing by Mobile Entities, 335-370.
Czyzowicz2019Plane
Jurek Czyzowicz, Maxime Godon, Evangelos Kranakis, Arnaud Labourel (2019). Group search of the plane with faulty robots. Theoretical Computer Science 792, pp. 69-84.
Das2019Survey
Shantanu Das (2019). Graph Explorations with Mobile Agents. Distributed Computing by Mobile Entities, LNCS 11340, pp. 403–422.
Disser2019Pebbles
Yann Disser, Jan Hackfeld, Max Klimm (2019). Tight bounds for undirected graph exploration with pebbles and multiple agents. Journal of the ACM 66(6) (pebble results first at SODA 2016, pp. 25–39).
Disser2019Second
Yann Disser, Sören Schmitt (2019). Evacuating Two Robots from a Disk: A Second Cut. SIROCCO 2019, pp. 200–214.
Emek2019Deterministic
Yuval Emek, Shay Kutten, Ron Lavi, William K. Moses Jr. (2019). Deterministic Leader Election in Programmable Matter. ICALP 2019 (LIPIcs 132), 140.
Flocchini2019Synchronous
Paola Flocchini, Nicola Santoro, Koichi Wada (2019). On Memory, Communication, and Synchronous Schedulers When Moving and Computing. OPODIS 2019, LIPIcs 153, 25:1–25:17.
Gastineau2019Leader
Nicolas Gastineau, Wahabou Abdou, Nader Mbarek, Olivier Togni (2019). Distributed Leader Election and Computation of Local Identifiers for Programmable Matter. ALGOSENSORS 2018, LNCS.
Georgiou2019SearchFetch
Konstantinos Georgiou, George Karakostas, Evangelos Kranakis (2019). Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models. Discrete Mathematics & Theoretical Computer Science 21(3).
Conference version at ICORES 2017, doi:10.5220/0006091600150026.
Kshemkalyani2019Efficient
Ajay D. Kshemkalyani, Faizan Ali (2019). Efficient Dispersion of Mobile Robots on Graphs. ICDCN 2019.
doi:10.1145/3288599.3288610arXiv:1805.12242
cited in anonymous-n-agents, base, rooted, async, ring, anonymous-randomized, crash, byzantine, strong-byzantine
First paper with \(k \le n\), with asynchronous algorithms, and with an explicit termination column; proves the \(\Omega(k)\) time lower bound.
Kshemkalyani2019Fast
Ajay D. Kshemkalyani, Anisur Rahaman Molla, Gokarna Sharma (2019). Fast Dispersion of Mobile Robots on Arbitrary Graphs. ALGOSENSORS 2019 (LNCS 11931).
The paper states the time bound with a \(\log k\) factor; later papers restate it as \(\log \ell\). The arXiv preprint 1812.05352 covers both the ALGOSENSORS 2019 paper on arbitrary graphs and the WALCOM 2020 paper on grids.
Michail2019Transformation
Othon Michail, George Skretas, Paul G. Spirakis (2019). On the transformation capability of feasible mechanisms for programmable matter. Journal of Computer and System Sciences 102:18–39.
Molla2019Randomness
Anisur Rahaman Molla, William K. Moses Jr. (2019). Dispersion of Mobile Robots: The Power of Randomness. TAMC 2019 (LNCS 11436).
Pattanayak2019Chauffeuring
Debasish Pattanayak, H. Ramesh, Partha Sarathi Mandal (2019). Chauffeuring a Crashed Robot from a Disk. ALGOSENSORS 2019, pp. 177–191.
Pattanayak2019Crash
Debasish Pattanayak, Kaushik Mondal, H. Ramesh, Partha Sarathi Mandal (2019). Gathering of mobile robots with weak multiplicity detection in presence of crash-faults. Journal of Parallel and Distributed Computing 123:145–155 (ICDCN 2017).
Pelc2019Survey
Andrzej Pelc (2019). Deterministic rendezvous algorithms. Distributed Computing by Mobile Entities, LNCS 11340, pp. 423–454.
Acharjee2019Shoreline
Sumi Acharjee, Konstantinos Georgiou, Somnath Kundu, Akshaya Srinivasan (2020). Lower Bounds for Shoreline Searching With 2 or More Robots. OPODIS 2019, LIPIcs 153, 26:1–26:11.
Almethen2020Pushing
Abdullah Almethen, Othon Michail, Igor Potapov (2020). Pushing lines helps: Efficient universal centralised transformations for programmable matter. Theoretical Computer Science 830–831:43–59.
Conference version at ALGOSENSORS 2019.
Bose2020Fat
Kaustav Bose, Ranendu Adhikary, Manash Kumar Kundu, Buddhadeb Sau (2020). Arbitrary Pattern Formation by Opaque Fat Robots with Lights. CALDAM 2020, LNCS 12016, pp. 347–359.
Brandt2020Rays
Sebastian Brandt, Klaus-Tycho Foerster, Benjamin Richner, Roger Wattenhofer (2020). Wireless evacuation on m rays with k searchers. Theoretical Computer Science 811:56–69.
Conference version at SIROCCO 2017.
Chuangpishit2020MultiObjective
Huda Chuangpishit, Konstantinos Georgiou, Preeti Sharma (2020). A Multi-Objective Optimization Problem on Evacuating 2 Robots from the Disk in the Face-to-Face Model; Trade-Offs between Worst-Case and Average-Case Analysis. Information 11, 506.
Chuangpishit2020Triangles
Huda Chuangpishit, Saeed Mehrabi, Lata Narayanan, Jaroslav Opatrny (2020). Evacuating equilateral triangles and squares in the face-to-face model. Computational Geometry 89:101624.
Czyzowicz2020FaceToFace
Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Lata Narayanan, Jaroslav Opatrny, Birgit Vogtenhuber (2020). Evacuating Robots from a Disk Using Face-to-Face Communication. Discrete Mathematics & Theoretical Computer Science 22(4) (CIAC 2015).
DAngelo2020Silent
Gianlorenzo D'Angelo, Mattia D'Emidio, Shantanu Das, Alfredo Navarra, Giuseppe Prencipe (2020). Asynchronous Silent Programmable Matter Achieves Leader Election and Compaction. IEEE Access 8:207619–207634 (AAMAS 2020).
Das2020Luminous
Shantanu Das, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro (2020). Forming Sequences of Patterns With Luminous Robots. IEEE Access 8:90577–90597.
Conference version at FUN 2014.
Daymude2020Hull
Joshua J. Daymude, Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Christian Scheideler, Andréa W. Richa (2020). Convex Hull Formation for Programmable Matter. ICDCN 2020, 2:1–2:10.
DiLuna2020Dynamic
Giuseppe A. Di Luna, Stefan Dobrev, Paola Flocchini, Nicola Santoro (2020). Distributed exploration of dynamic rings. Distributed Computing 33(1):41–67 (ICDCS 2016).
DiLuna2020MobileRAM
Giuseppe Antonio Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, Yukiko Yamauchi (2020). Mobile RAM and Shape Formation by Programmable Particles. Euro-Par 2020, LNCS, pp. 343–358.
DiLuna2020Shape
Giuseppe A. Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, Yukiko Yamauchi (2020). Shape formation by programmable particles. Distributed Computing 33:69–101 (OPODIS 2017).
Disser2020General
Yann Disser, Frank Mousset, Andreas Noever, Nemanja Škorić, Angelika Steger (2020). A general lower bound for collaborative tree exploration. Theoretical Computer Science 811:70–78 (SIROCCO 2017).
Dobrev2020Shoreline
Stefan Dobrev, Rastislav Královič, Dana Pardubská (2020). Improved Lower Bounds for Shoreline Search. Structural Information and Communication Complexity, pp. 80-90.
Gmyr2020Tile
Robert Gmyr, Kristian Hinnenthal, Irina Kostitsyna, Fabian Kuhn, Dorian Rudolph, Christian Scheideler, Thim Strothmann (2020). Forming tile shapes with simple robots. Natural Computing 19:375–390.
doi:10.1007/s11047-019-09774-2
cited in planar
Conference version at DNA 24 (2018), doi:10.1007/978-3-030-00030-1_8; first presented at EuroCG 2017 (non-archival), which the timeline counts as first appearance.
Hideg2020Filling
Attila Hideg, Tamás Lukovszki (2020). Asynchronous filling by myopic luminous robots. ALGOSENSORS 2020, LNCS, pp. 108–123.
Metadata from Crossref. arXiv version in papers/; abstract read.
Kawamura2020Simple
Akitoshi Kawamura, Makoto Soejima (2020). Simple strategies versus optimal schedules in multi-agent patrolling. Theoretical Computer Science 839:195–206.
Kshemkalyani2020Dynamic
Ajay D. Kshemkalyani, Anisur Rahaman Molla, Gokarna Sharma (2020). Efficient Dispersion of Mobile Robots on Dynamic Graphs. ICDCS 2020.
Kshemkalyani2020Global
Ajay D. Kshemkalyani, Anisur Rahaman Molla, Gokarna Sharma (2020). Dispersion of Mobile Robots in the Global Communication Model. ICDCN 2020.
The DFS bound claimed here (\(O(\min(m,k\Delta))\) time with \(O(\log(k+\Delta))\) bits) is weakened in the journal version; cite Kshemkalyani et al. 2022 for the DFS bounds.
Kshemkalyani2020Grids
Ajay D. Kshemkalyani, Anisur Rahaman Molla, Gokarna Sharma (2020). Dispersion of Mobile Robots on Grids. WALCOM 2020 (LNCS 12049).
The arXiv version (shared with Kshemkalyani et al. 2019) says the agents have no consistent compass; later papers describe this setting as an oriented grid. To be checked against the WALCOM text. The arXiv preprint 1812.05352 covers both the ALGOSENSORS 2019 paper on arbitrary graphs and the WALCOM 2020 paper on grids.
Lamprou2020Fast
Ioannis Lamprou, Russell Martin, Sven Schewe (2020). Fast two-robot disk evacuation with wireless communication. Theoretical Computer Science 846:38–60.
Conference version at DISC 2016, doi:10.1007/978-3-662-53426-7_1.
Molla2020WeakRing
Anisur Rahaman Molla, Kaushik Mondal, William K. Moses Jr. (2020). Efficient Dispersion on an Anonymous Ring in the Presence of Weak Byzantine Robots. ALGOSENSORS 2020 (LNCS 12503); journal version: Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots, Theoretical Computer Science 887:111–121, 2021 (doi:10.1016/j.tcs.2021.07.008).
Mondal2020Uniform
Moumita Mondal, Sruti Gan Chaudhuri, Ayan Dutta, Krishnendu Mukhopadhyaya, Punyasha Chatterjee (2020). Uniform Circle Formation By Oblivious Swarm Robots. arXiv preprint.
arXiv:2012.07113
cited in fat-async-limited
Preprint, not peer reviewed.
Pattanayak2020Collaborative
Debasish Pattanayak, H. Ramesh, Partha Sarathi Mandal (2020). Collaborative Evacuation of Mobile Robots. Proceedings of the 21st International Conference on Distributed Computing and Networking, 1-1.
Shintaku2020Knowledge
Takahiro Shintaku, Yuichi Sudo, Hirotsugu Kakugawa, Toshimitsu Masuzawa (2020). Efficient Dispersion of Mobile Agents without Global Knowledge. SSS 2020 (LNCS 12514).
Sun2020Byzantine
Xiaoming Sun, Yuan Sun, Jialin Zhang (2020). Better Upper Bounds for Searching on a Line with Byzantine Robots. Complexity and Approximation, LNCS 12000, pp. 151–171.
Akitaya2021Musketeers
Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmović, Robin Flatland, Matias Korman, Belen Palop, Irene Parada, André van Renssen, Vera Sacristán (2021). Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers. Algorithmica 83:1316–1351.
Bhagat2021kCircle
Subhash Bhagat, Bibhuti Das, Abhinav Chakraborty, Krishnendu Mukhopadhyaya (2021). k-Circle Formation and k-epf by Asynchronous Robots. Algorithms 14(2):62.
doi:10.3390/a14020062
cited in k-epf
Bose2021Opaque
Kaustav Bose, Manash Kumar Kundu, Ranendu Adhikary, Buddhadeb Sau (2021). Arbitrary pattern formation by asynchronous opaque robots with lights. Theoretical Computer Science 849:138–158 (SIROCCO 2019).
Bramas2020Poleless
Quentin Bramas, Pascal Lafourcade, Stéphane Devismes (2021). Finding water on Poleless using melomaniac myopic chameleon robots. FUN 2021 (LIPIcs 157), 6:1–6:19.
Metadata from DataCite (FUN 2020 was held in 2021; the key keeps the file name in papers/). Abstract read.
Bramas2021Infinite
Quentin Bramas, Stéphane Devismes, Pascal Lafourcade (2021). Infinite grid exploration by disoriented robots. NETYS 2020, LNCS, pp. 129–145 (brief announcement at SIROCCO 2019, pp. 340–344).
Metadata from Crossref (SIROCCO brief announcement doi 10.1007/978-3-030-24922-9_25). arXiv version in papers/; abstract read. A journal follow-up without chirality is Discrete Applied Mathematics 375:193–214 (2025), doi 10.1016/j.dam.2025.05.031, not read.
Czyzowicz2021Byzantine
Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Sunil Shende (2021). Search on a line by Byzantine robots. International Journal of Foundations of Computer Science 32 (2021) 369–387.
arXiv:1611.08209
cited in line-byzantine
Journal details from the research notes; DOI not checked.
Czyzowicz2021GroupEvacuation
Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, Sunil Shende (2021). Group Evacuation on a Line by Agents with Different Communication Abilities. ISAAC 2021, LIPIcs 212, 57:1–57:24.
Czyzowicz2021NearMajority
Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Grzegorz Stachowiak (2021). Search and evacuation with a near majority of faulty agents. SIAM Conference on Applied and Computational Discrete Algorithms (ACDA 2021).
Czyzowicz2021TimeEnergy
Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny, Sunil Shende (2021). Time-energy tradeoffs for evacuation by two robots in the wireless model. Theoretical Computer Science 852, 61-72.
Das2021FiniteMemory
Archak Das, Avisek Sharma, Buddhadeb Sau (2021). Power of Finite Memory and Finite Communication Robots under Asynchronous Scheduler. arXiv preprint.
Preprint, not peer reviewed.
Das2021MemoryOptimal
Archak Das, Kaustav Bose, Buddhadeb Sau (2021). Memory Optimal Dispersion by Anonymous Mobile Robots. CALDAM 2021; journal version: Discrete Applied Mathematics 340:171–182, 2023 (doi:10.1016/j.dam.2023.07.005).
Daymude2021Energy
Joshua J. Daymude, Andréa W. Richa, Jamison W. Weber (2021). Bio-Inspired Energy Distribution for Programmable Matter. ICDCN 2021, pp. 86–95.
Devillez2021Tree
Henri Devillez, Béni Egressy, Robin Fritsch, Roger Wattenhofer (2021). Two-Agent Tree Evacuation. SIROCCO 2021, LNCS, pp. 204–221.
Dufoulon2021Efficient
Fabien Dufoulon, Shay Kutten, William K. Moses Jr. (2021). Efficient Deterministic Leader Election for Programmable Matter. PODC 2021, pp. 103–113.
Erlebach2021Temporal
Thomas Erlebach, Michael Hoffmann, Frank Kammer (2021). On temporal graph exploration. Journal of Computer and System Sciences 119:1–18 (ICALP 2015).
Georgiou2021Treasure
Konstantinos Georgiou, George Karakostas, Evangelos Kranakis (2021). Treasure evacuation with one robot on a disk. Theoretical Computer Science 852:18–28.
Conference version at ALGOSENSORS 2016, doi:10.1007/978-3-319-53058-1_6.
Gotoh2021Dynamic
Tsuyoshi Gotoh, Paola Flocchini, Toshimitsu Masuzawa, Nicola Santoro (2021). Exploration of dynamic networks: Tight bounds on the number of agents. Journal of Computer and System Sciences 122:1–18 (OPODIS 2019).
doi:10.1016/j.jcss.2021.04.003
cited in temporal
Jawhar2021Bike
Khaled Jawhar, Evangelos Kranakis (2021). Bike Assisted Evacuation on a Line. Lecture Notes in Computer Science SOFSEM 2021: Theory and Practice of Computer Science, 104-118.
Kshemkalyani2021NearOptimal
Ajay D. Kshemkalyani, Gokarna Sharma (2021). Near-Optimal Dispersion on Arbitrary Anonymous Graphs. OPODIS 2021 (LIPIcs 217); journal version: Journal of Computer and System Sciences 152:103656, 2025 (doi:10.1016/j.jcss.2025.103656).
Molla2021ByzantineGraphs
Anisur Rahaman Molla, Kaushik Mondal, William K. Moses Jr. (2021). Byzantine Dispersion on Graphs. IPDPS 2021.
Nakai2021Asynchronous
Rikuo Nakai, Yuichi Sudo, Koichi Wada (2021). Asynchronous Gathering Algorithms for Autonomous Mobile Robots with Lights. SSS 2021, LNCS, pp. 410–424.
Pattanayak2021Tolerating
Debasish Pattanayak, Gokarna Sharma, Partha Sarathi Mandal (2021). Dispersion of Mobile Robots Tolerating Faults. ICDCN 2021 Adjunct (WDALFR workshop).
doi:10.1145/3427477.3429464
cited in crash
Poudel2021FaultTolerant
Pavan Poudel, Aisha Aljohani, Gokarna Sharma (2021). Fault-tolerant complete visibility for asynchronous robots with lights under one-axis agreement. Theoretical Computer Science 850:116–134.
Poudel2021TimeOptimal
Pavan Poudel, Gokarna Sharma (2021). Time-Optimal Gathering under Limited Visibility with One-Axis Agreement. Information 12(11):448 (SSS 2017).
doi:10.3390/info12110448
cited in limited-one-axis
Rauch2021Chirality
Arthur Rauch, Quentin Bramas, Stéphane Devismes, Pascal Lafourcade, Anissa Lamani (2021). Optimal exclusive perpetual grid exploration by luminous myopic robots without common chirality. NETYS 2021, LNCS, pp. 95–110.
doi:10.1007/978-3-030-91014-3_7link
cited in grid-fsync-perpetual, grid-async-perpetual-phi2, grid-async-perpetual-phi3
Metadata from Crossref. Not read (the HAL record has no file); results as reported in Table 1 of Darwich et al. 2023 and in the related work of Bramas et al. 2026.
Sharma2021Constant
Gokarna Sharma, Ramachandran Vaidyanathan, Jerry L. Trahan (2021). Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case. Algorithms 14(2):56.
doi:10.3390/a14020056
cited in lights-async-time
Bhagat2022Meet
Subhash Bhagat, Andrzej Pelc (2022). How to Meet at a Node of Any Connected Graph. DISC 2022, LIPIcs 246, 11:1–11:16.
Metadata from DataCite. Abstract, introduction and model read (open access). First synchronous rendezvous algorithm for locally finite, possibly infinite graphs; used for the rendezvous graph-size axis.
Bojko2022Dual
Dominik Bojko, Karol Gotfryd, Dariusz R. Kowalski, Dominik Pająk (2022). Tree Exploration in Dual-Memory Model. MFCS 2022 (LIPIcs 241), 22:1–22:16.
doi:10.4230/LIPIcs.MFCS.2022.22arXiv:2112.13449
cited in recolourable, recolourable-cactus, recolourable-trees, label-guided
Metadata from DataCite and arXiv. Abstract and introduction read.
Bouchard2022Polynomial
Sébastien Bouchard, Yoann Dieudonné, Anissa Lamani (2022). Byzantine gathering in polynomial time. Distributed Computing 35(3):235–263 (ICALP 2018).
Bramas2022Beedroids
Quentin Bramas, Stéphane Devismes, Anaïs Durand, Pascal Lafourcade, Anissa Lamani (2022). Beedroids: how luminous autonomous swarms of UAVs can save the world?. FUN 2022 (LIPIcs 226), 7:1–7:21.
Metadata from DataCite. A copy is in papers/; abstract read.
Buchin2022Energy
Kevin Buchin, Paola Flocchini, Irina Kostitsyna, Tom Peters, Nicola Santoro, Koichi Wada (2022). On the Computational Power of Energy-Constrained Mobile Robots: Algorithms and Cross-Model Analysis. SIROCCO 2022, LNCS 13298, pp. 42–61.
Journal version: Information and Computation 303:105280 (2025), doi:10.1016/j.ic.2025.105280.
Castenow2022Unifying
Jannik Castenow, Jonas Harbig, Daniel Jung, Peter Kling, Till Knollmann, Friedhelm Meyer auf der Heide (2022). A unifying approach to efficient (near)-gathering of disoriented robots with limited visibility. OPODIS 2022 (LIPIcs 253), 15:1–15:25.
Das2022Landmark
Archak Das, Kaustav Bose, Buddhadeb Sau (2022). Exploring a dynamic ring without landmark. Theoretical Computer Science 929:191–205 (SSS 2021).
Georgiou2022Asymmetric
Konstantinos Georgiou, Nikos Giachoudis, Evangelos Kranakis (2022). Evacuation from a Disk for Robots with Asymmetric Communication. ISAAC 2022 (LIPIcs 248), 19:1–19:16.
Gorain2022Pebble
Barun Gorain, Kaushik Mondal, Himadri Nayak, Supantha Pandit (2022). Pebble guided optimal treasure hunt in anonymous graphs. Theoretical Computer Science 922:61–80 (SIROCCO 2021).
Gorain2022Silent
Barun Gorain, Partha Sarathi Mandal, Kaushik Mondal, Supantha Pandit (2022). Collaborative Dispersion by Silent Robots. SSS 2022 (LNCS 13751); journal version: Journal of Parallel and Distributed Computing 188:104852, 2024 (doi:10.1016/j.jpdc.2024.104852).
Italiano2022Directed
Giuseppe F. Italiano, Debasish Pattanayak, Gokarna Sharma (2022). Dispersion of Mobile Robots on Directed Anonymous Graphs. SIROCCO 2022 (LNCS 13298); journal version: Journal of Parallel and Distributed Computing 204:105139, 2025 (doi:10.1016/j.jpdc.2025.105139), which adds the deficiency-based algorithm.
Journal version: Journal of Parallel and Distributed Computing 204:105139 (2025), doi:10.1016/j.jpdc.2025.105139, open access; it adds the deficiency-based algorithm and the lower bounds.
Kedia2022Alignment
Hridesh Kedia, Shunhao Oh, Dana Randall (2022). Local Stochastic Algorithms for Alignment in Self-Organizing Particle Systems. APPROX/RANDOM 2022, LIPIcs 245, 14.
Kshemkalyani2022GlobalJ
Ajay D. Kshemkalyani, Anisur Rahaman Molla, Gokarna Sharma (2022). Dispersion of mobile robots using global communication. Journal of Parallel and Distributed Computing 161:100–117.
doi:10.1016/j.jpdc.2021.11.007
cited in global
Journal version of Kshemkalyani et al. 2020.
Liu2022Square
Luan Liu, Qi Wei, Yan Zhang, Jie Sun, Wenxin Zhang (2022). Online Algorithm for Evacuating Crashed Faulty Robots from A Square. 2022 IEEE 8th International Conference on Computer and Communications (ICCC), 2276-2280.
Nagahama2022Grid
Shota Nagahama, Fukuhito Ooshita, Michiko Inoue (2022). Terminating grid exploration with myopic luminous robots. International Journal of Networking and Computing 12(1):73–102 (APDCM 2021, IPDPS Workshops, pp. 586–595).
doi:10.15803/ijnc.12.1_73
cited in grid-fsync-stop-chirality, grid-fsync-stop, grid-fsync-stop-chirality-phi2, grid-fsync-stop-phi2, grid-async-stop-chirality, grid-async-stop, grid-async-stop-chirality-phi2, grid-async-stop-phi2
Metadata from Crossref (workshop version doi 10.1109/IPDPSW52791.2021.00092). Checked against the full journal text: model, Table 1, Theorem 1 and the algorithm statements of Section 4.
Ooshita2022Ring
Fukuhito Ooshita, Sébastien Tixeuil (2022). Ring exploration with myopic luminous robots. Information and Computation 285:104702 (SSS 2018, LNCS, pp. 301–316).
doi:10.1016/j.ic.2021.104702arXiv:1805.03965
cited in ring-fsync-perpetual, ring-fsync-stop, ring-async-perpetual, ring-async-stop
Metadata from Crossref (journal and SSS 2018 version, doi 10.1007/978-3-030-03232-6_20). Checked against the full text of the arXiv version (May 2018): model, Table 1, Theorems 3–18 and conclusion.
Shimoyama2022Cactus
Kohei Shimoyama, Yuichi Sudo, Hirotsugu Kakugawa, Toshimitsu Masuzawa (2022). One Bit Agent Memory is Enough for Snap-Stabilizing Perpetual Exploration of Cactus Graphs with Distinguishable Cycles. SSS 2022 (invited paper), LNCS 13751, pp. 19–34.
Metadata from Crossref. Not read; only the title and the description in Hiraoka et al. 2026.
Alsaedi2022Fat
Rusul J. Alsaedi, Joachim Gudmundsson, André van Renssen (2023). The Mutual Visibility Problem for Fat Robots. WADS 2023, LNCS 14079, pp. 15–28.
arXiv version 3 (2026) is titled "The Mutual Visibility Problem for Fat Robots with Lights".
Bockenhauer2023Inports
Hans-Joachim Böckenhauer, Fabian Frei, Walter Unger, David Wehner (2023). Zero-Memory Graph Exploration with Unknown Inports. SIROCCO 2023, LNCS 13892, pp. 246–261.
doi:10.1007/978-3-031-32733-9_11arXiv:2301.13860
cited in recolourable, once, once-known-n, once-trees
Metadata from Crossref and arXiv. Checked against the full text (arXiv v1): model (Section 1.2), Theorems 1–9, 11 and the conclusion. Colour counts in this paper exclude the initial colour.
Bouchard2023Almost
Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel, Andrzej Pelc (2023). Almost-optimal deterministic treasure hunt in unweighted graphs. ACM Transactions on Algorithms 19(3) (ICALP 2021).
Bouchard2023Chatter
Sébastien Bouchard, Yoann Dieudonné, Andrzej Pelc (2023). Want to Gather? No Need to Chatter!. SIAM Journal on Computing 52(2):358–411 (PODC 2020).
Bramas2023Chirality
Quentin Bramas, Pascal Lafourcade, Stéphane Devismes (2023). Optimal exclusive perpetual grid exploration by luminous myopic opaque robots with common chirality. Theoretical Computer Science 977:114162 (ICDCN 2021, pp. 76–85).
doi:10.1016/j.tcs.2023.114162link
cited in grid-fsync-perpetual-chirality, grid-fsync-perpetual-chirality-phi2, grid-async-perpetual-chirality-phi2, grid-fsync-stop-chirality, grid-fsync-stop, grid-fsync-stop-chirality-phi2, grid-fsync-stop-phi2, grid-async-stop-chirality-phi2, grid-async-stop-phi2
Metadata from Crossref (ICDCN 2021 version doi 10.1145/3427796.3427834). Checked against the accepted manuscript on HAL: abstract, contribution, Table 1, model.
Bramas2023Indulgent
Quentin Bramas, Anissa Lamani, Sébastien Tixeuil (2023). Stand up indulgent gathering. Theoretical Computer Science 939:63–77.
Briones2023Asynchronous
Joseph L. Briones, Tishya Chhabra, Joshua J. Daymude, Andréa W. Richa (2023). Invited Paper: Asynchronous Deterministic Leader Election in Three-Dimensional Programmable Matter. ICDCN 2023, pp. 38–47.
Chand2023Cover
Prabhat Kumar Chand, Anisur Rahaman Molla, Sumathi Sivasubramaniam (2023). Run for Cover: Dominating Set via Mobile Agents. ALGOSENSORS 2023, pp. 133–150.
Chand2023FaultTolerant
Prabhat Kumar Chand, Manish Kumar, Anisur Rahaman Molla, Sumathi Sivasubramaniam (2023). Fault-Tolerant Dispersion of Mobile Robots. CALDAM 2023 (LNCS 13779); journal version: Discrete Applied Mathematics 377:299–313, 2025 (doi:10.1016/j.dam.2025.06.068).
Coleman2023Delivery
Jared Coleman, Evangelos Kranakis, Danny Krizanc, Oscar Morales-Ponce (2023). Delivery to Safety with Two Cooperating Robots. Lecture Notes in Computer Science SOFSEM 2023: Theory and Practice of Computer Science, 359-371.
Cosson2023BFDN
Romain Cosson, Laurent Massoulié, Laurent Viennot (2023). Efficient collaborative tree exploration with breadth-first depth-next. DISC 2023 (LIPIcs 281), paper 14.
Darwich2023Torus
Omar Darwich, Ahmet-Sefa Ulucan, Quentin Bramas, Anissa Lamani, Anaïs Durand, Pascal Lafourcade (2023). Perpetual torus exploration by myopic luminous robots. Theoretical Computer Science 976:114143 (SSS 2022, LNCS, pp. 164–177).
doi:10.1016/j.tcs.2023.114143link
cited in torus-fsync-perpetual-chirality, torus-fsync-perpetual, torus-fsync-perpetual-chirality-phi2, torus-fsync-perpetual-phi2
Metadata from Crossref (SSS 2022 version doi 10.1007/978-3-031-21017-4_11, which covers only common chirality). Checked against the accepted manuscript on HAL: contribution, Tables 1–2, model.
Daymude2023Canonical
Joshua J. Daymude, Andréa W. Richa, Christian Scheideler (2023). The canonical amoebot model: algorithms and concurrency control. Distributed Computing 36:159–192 (DISC 2021).
Defago2023ModelChecking
Xavier Défago, Adam Heriban, Sébastien Tixeuil, Koichi Wada (2023). Using model checking to formally verify rendezvous algorithms for robots with lights in Euclidean space. Robotics and Autonomous Systems 163:104378.
Conference version at SRDS 2020, doi:10.1109/SRDS51746.2020.00019.
Feletti2023Log
Caterina Feletti, Carlo Mereghetti, Beatrice Palano (2023). \(O(\log n)\)-time uniform circle formation for asynchronous opaque luminous robots. OPODIS 2023 (LIPIcs 286), 5:1–5:21.
Feletti2023Schedulers
Caterina Feletti, Carlo Mereghetti, Beatrice Palano (2023). Uniform circle formation for fully, semi-, and asynchronous opaque robots with lights. Applied Sciences 13(13):7991.
Conference version at ICTCS 2022 (CEUR Workshop Proceedings 3284, pp. 207–221).
Flocchini2023Asynchrony
Paola Flocchini, Nicola Santoro, Yuichi Sudo, Koichi Wada (2023). On Asynchrony, Memory, and Communication: Separations and Landscapes. OPODIS 2023, LIPIcs 286, 28:1–28:23.
Georgiou2023Lp
Konstantinos Georgiou, Sean Leizerovich, Jesse Lucier, Somnath Kundu (2023). Evacuating from \(\ell_p\) unit disks in the wireless model. Theoretical Computer Science 944:113675.
Conference version at ALGOSENSORS 2021, doi:10.1007/978-3-030-89240-1_6.
Georgiou2023OptimalCircle
Konstantinos Georgiou, Evangelos Kranakis, Nikos Leonardos, Aris Pagourtzis, Ioannis Papaioannou (2023). Optimal circle search despite the presence of faulty robots. Information Processing Letters 182, 106391.
Georgiou2023WeightedLine
Konstantinos Georgiou, Jesse Lucier (2023). Weighted group search on a line & implications to the priority evacuation problem. Theoretical Computer Science 939, 1-17.
Inoue2022Oblivious
Taichi Inoue, Naoki Kitamura, Taisuke Izumi, Toshimitsu Masuzawa (2023). Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected Graphs. OPODIS 2022 (LIPIcs 253), 11:1–11:18.
Metadata from DataCite. Abstract read.
Kostitsyna2023Fast
Irina Kostitsyna, Tom Peters, Bettina Speckmann (2023). Fast Reconfiguration for Programmable Matter. DISC 2023, LIPIcs 281, 27.
Leonardos2023Symmetric
Nikos Leonardos, Aris Pagourtzis, Ioannis Papaioannou (2023). Byzantine fault tolerant symmetric-persistent circle evacuation. Theoretical Computer Science 956:113839.
Conference version at ALGOSENSORS 2021, doi:10.1007/978-3-030-89240-1_8.
Mandal2023Live
Subhrangsu Mandal, Anisur Rahaman Molla, William K. Moses Jr. (2023). Efficient live exploration of a dynamic ring with mobile robots. Theoretical Computer Science 980:114201.
Molla2023Fast
Anisur Rahaman Molla, Kaushik Mondal, William K. Moses Jr. (2023). Fast Deterministic Gathering with Detection on Arbitrary Graphs: The Power of Many Robots. IPDPS 2023, pp. 47–57.
Nagahama2023Ring
Shota Nagahama, Fukuhito Ooshita, Michiko Inoue (2023). Ring exploration of myopic luminous robots with visibility more than one. Information and Computation 292:105036 (SSS 2019, LNCS, pp. 256–271).
Metadata from Crossref (SSS 2019 version: doi 10.1007/978-3-030-34992-9_20). Not read: no open copy found (ScienceDirect refused automated access; the IPSJ technical report AL-173 is members-only). Results as reported in Table 1 of Ooshita et al. 2025 and in the introduction of Nagahama et al. 2022.
Okumura2023External
Takashi Okumura, Koichi Wada, Xavier Défago (2023). Optimal L-algorithms for rendezvous of asynchronous mobile robots with external-lights. Theoretical Computer Science 979:114198.
Conference version at OPODIS 2018, LIPIcs 125, 24:1–24:16, doi:10.4230/LIPIcs.OPODIS.2018.24.
Pattanayak2023Spite
Debasish Pattanayak, Gokarna Sharma, Partha Sarathi Mandal (2023). Dispersion of Mobile Robots in Spite of Faults. SSS 2023 (LNCS 14310).
doi:10.1007/978-3-031-44274-2_31
cited in crash
Pramanick2023MIS
Subhajit Pramanick, Sai Vamshi Samala, Debasish Pattanayak, Partha Sarathi Mandal (2023). Distributed algorithms for filling MIS vertices of an arbitrary graph by myopic luminous robots. Theoretical Computer Science 978:114187 (ICDCIT 2023, LNCS, pp. 3–19, as “Filling MIS Vertices of a Graph by Myopic Luminous Robots”).
Metadata from Crossref (ICDCIT version doi 10.1007/978-3-031-24848-1_1). arXiv version in papers/; abstract read.
Seike2023Separation
Hirokazu Seike, Yukiko Yamauchi (2023). Separation of Unconscious Colored Robots. SSS 2023, pp. 328–343.
doi:10.1007/978-3-031-44274-2_24
cited in async
Abstract not read; results as summarised by Flocchini et al. 2024.
Terai2023Gathering
Satoshi Terai, Koichi Wada, Yoshiaki Katayama (2023). Gathering problems for autonomous mobile robots with lights. Theoretical Computer Science 941:241–261.
Weber2023Energy
Jamison W. Weber, Tishya Chhabra, Andréa W. Richa, Joshua J. Daymude (2023). Energy-Constrained Programmable Matter Under Unfair Adversaries. OPODIS 2023, LIPIcs 286, 7:1–7:21.
Banerjee2024UnorientedGrids
Rik Banerjee, Manish Kumar, Anisur Rahaman Molla (2024). Optimizing Robot Dispersion on Unoriented Grids: With and Without Fault Tolerance. ALGOWIN 2024 (LNCS 15026).
Bhagat2024Fat
Subhash Bhagat, Paulomi Dey, Rajarshi Ray (2024). Collision-Free Linear Time Mutual Visibility for Asynchronous Fat Robots. ICDCN 2024, pp. 84–93.
doi:10.1145/3631461.3631544
cited in fat
Cosson2024Mining
Romain Cosson (2024). Breaking the k/log k barrier in collective tree exploration via tree-mining. SODA 2024, pp. 4264–4282.
Cosson2024Potential
Romain Cosson, Laurent Massoulié (2024). Collective tree exploration via potential function method. ITCS 2024 (LIPIcs), paper 35.
Das2024Visibility
Archak Das, Satakshi Ghosh, Avisek Sharma, Pritam Goswami, Buddhadeb Sau (2024). The Computational Landscape of Autonomous Mobile Robots: The Visibility Perspective. ICDCIT 2024, LNCS, pp. 85–100.
Feletti2024Optimal
Caterina Feletti, Debasish Pattanayak, Gokarna Sharma (2024). Brief announcement: optimal uniform circle formation by asynchronous luminous robots. DISC 2024 (LIPIcs 319), 46:1–46:7; full version arXiv 2405.06617; journal version J. Parallel Distrib. Comput. 218:105338 (2026).
Flocchini2025Separation
Paola Flocchini, Debasish Pattanayak, Francesco Piselli, Nicola Santoro, Yukiko Yamauchi (2024). Asynchronous Separation of Unconscious Colored Robots. CANDAR Workshops 2024, pp. 183–189; journal: International Journal of Networking and Computing 15(2), 2025.
doi:10.1109/CANDARW64572.2024.00037
cited in async
Georgiou2024Disoriented
Konstantinos Georgiou, Nikos Giachoudis, Evangelos Kranakis (2024). Overcoming probabilistic faults in disoriented linear search. Theoretical Computer Science 1014:114761.
Hahn2024Large
Christopher Hahn, Jonas Harbig, Peter Kling (2024). Forming large patterns with local robots in the OBLOT model. SAND 2024 (LIPIcs 292), 14:1–14:20.
Hinnenthal2024Shape3D
Kristian Hinnenthal, David Liedtke, Christian Scheideler (2024). Efficient Shape Formation by 3D Hybrid Programmable Matter: An Algorithm for Low Diameter Intermediate Structures. SAND 2024, LIPIcs 292, 15.
Kamei2024MIS
Sayaka Kamei, Sébastien Tixeuil (2024). An asynchronous maximum independent set algorithm by myopic luminous robots on grids. The Computer Journal 67(1):57–77 (advance access 2022).
Metadata from Crossref. arXiv version in papers/; abstract read.
Kirkpatrick2024Separating
David Kirkpatrick, Irina Kostitsyna, Alfredo Navarra, Giuseppe Prencipe, Nicola Santoro (2024). On the power of bounded asynchrony: convergence by autonomous robots with limited visibility. Distributed Computing 37(3):279–308 (PODC 2021, as "Separating bounded and unbounded asynchrony for autonomous robots: point convergence with limited visibility").
Kostitsyna2024Coating3D
Irina Kostitsyna, David Liedtke, Christian Scheideler (2024). Universal Coating by 3D Hybrid Programmable Matter. SIROCCO 2024, LNCS, pp. 384–401.
Kranakis2024Survey
Evangelos Kranakis (2024). Invited Paper: A Survey of the Impact of Knowledge on the Competitive Ratio in Linear Search. Stabilization, Safety, and Security of Distributed Systems, pp. 23-38.
Kshemkalyani2024AgentLE
Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, Gokarna Sharma (2024). Brief Announcement: Agent-Based Leader Election, MST, and Beyond. DISC 2024 brief announcement (LIPIcs 319), 50:1–50:7.
Moses2024Shepherd
William K. Moses Jr., Amanda Redlich (2024). Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd. ICDCN 2024.
Nakajima2024Simulations
Keita Nakajima, Kaito Takase, Koichi Wada (2024). Efficient Self-stabilizing Simulations of Energy-Restricted Mobile Robots by Asynchronous Luminous Mobile Robots. SSS 2024, LNCS, pp. 141–155.
Oh2024Bridge
Shunhao Oh, Joseph L. Briones, Jacob Calvert, Noah Egan, Dana Randall, Andréa W. Richa (2024). Single Bridge Formation in Self-Organizing Particle Systems. DISC 2024, LIPIcs 319, 34.
Pattanayak2024Memoryless
Debasish Pattanayak, Andrzej Pelc (2024). Graph exploration by a deterministic memoryless automaton with pebbles. Discrete Applied Mathematics 356:149–160.
Pattanayak2024MIS
Debasish Pattanayak, Subhash Bhagat, Sruti Gan Chaudhuri, Anisur Rahaman Molla (2024). Maximal Independent Set via Mobile Agents. ICDCN 2024, pp. 74–83.
doi:10.1145/3631461.3631543
cited in known-n-delta
Pattanayak2024TimeColor
Debasish Pattanayak, Gokarna Sharma (2024). Time-color tradeoff on uniform circle formation by asynchronous robots. IPDPS 2024, pp. 987–997.
Pattanayak2024Treasure
Debasish Pattanayak, Andrzej Pelc (2024). Deterministic treasure hunt and rendezvous in arbitrary connected graphs. Information Processing Letters 185:106455.
Sudo2024NearLinear
Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yonghwan Kim, Toshimitsu Masuzawa (2024). Near-Linear Time Dispersion of Mobile Agents. DISC 2024 (LIPIcs 319); journal version: Distributed Computing 39(1), 2026 (doi:10.1007/s00446-025-00494-8).
Alsaedi2025Pattern
Rusul J. Alsaedi, Joachim Gudmundsson, André van Renssen (2025). Pattern formation for fat robots with lights. Computational Geometry 128:102161.
Asahiro2025MAS
Yuichi Asahiro, Masafumi Yamashita (2025). Minimum algorithm sizes for the gathering and related problems of autonomous mobile robots. Theoretical Computer Science 1051:115397 (SSS 2023).
Banerjee2025OrientedGridsFT
Rik Banerjee, Manish Kumar, Anisur Rahaman Molla (2025). Optimal Fault-Tolerant Dispersion on Oriented Grids. ICDCN 2025.
Behrouz2025Byzantine
Pourandokht Behrouz, Orestis Konstantinidis, Nikos Leonardos, Aris Pagourtzis, Ioannis Papaioannou, Marianna Spyrakou (2025). Byzantine fault-tolerant protocols for (n,f)-evacuation from a circle. Theoretical Computer Science 1038:115185.
Conference version at ALGOWIN 2023, doi:10.1007/978-3-031-48882-5_7.
Borowiecki2025Discrete
Piotr Borowiecki, Shantanu Das, Dariusz Dereniowski, Łukasz Kuszner (2025). Discrete evacuation in graphs with multiple exits. Theoretical Computer Science 1035, pp. 115141.
Bramas2025TradeOff
Quentin Bramas, Hirotsugu Kakugawa, Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Masahiro Shibata, Sébastien Tixeuil (2025). A visibility vs. memory trade-off for stand-up indulgent gathering on lines. SIROCCO 2025, LNCS, pp. 159–175.
Metadata from Crossref. A copy is in papers/; abstract read.
Chalopin2025SelfStab
Jérémie Chalopin, Shantanu Das, Maria Kokkou (2025). Deterministic self-stabilising leader election for programmable matter with constant memory. Distributed Computing.
Chand2025Butterfly
Prabhat Kumar Chand, Apurba Das, Anisur Rahaman Molla (2025). Brief Announcement: Distributed Butterfly Analysis using Mobile Agents. SPAA 2025 brief announcement, pp. 623–627.
Chand2025Trees
Prabhat Kumar Chand, Manish Kumar, Anisur Rahaman Molla (2025). Computing Tree Structures in Anonymous Graphs via Mobile Agents. SSS 2025, pp. 111–127.
Conley2025Inspection
James Conley, Konstantinos Georgiou (2025). Multi-agent Disk Inspection. Lecture Notes in Computer Science Structural Information and Communication Complexity, 262-280.
Cosson2025Asynchronous
Romain Cosson, Laurent Massoulié (2025). Asynchronous collective tree exploration: a distributed algorithm, and a new lower bound. arXiv preprint.
No peer-reviewed version found.
Das2025MISGrid
Raja Das, Avisek Sharma, Buddhadeb Sau (2025). Maximum independent set formation on a finite grid by myopic robots. Theoretical Computer Science 1031:115077 (Intelligent Computing 2023, LNNS, pp. 1247–1267).
Metadata from Crossref (conference version doi 10.1007/978-3-031-37963-5_86). arXiv version in papers/; abstract read.
Das2025SilentRing
Bibhuti Das, Barun Gorain, Kaushik Mondal, Krishnendu Mukhopadhyaya, Supantha Pandit (2025). Optimal Dispersion of Silent Robots in a Ring. SSS 2025 (LNCS); journal version: Theoretical Computer Science 1084:116171, 2026 (doi:10.1016/j.tcs.2026.116171).
Das2025Triangular
Raja Das, Pritam Goswami, Brati Mondal, Buddhadeb Sau (2025). Rectangle enclosed triangular grid exploration with myopic luminous robots. ICDCN 2025, pp. 249–253.
Metadata from Crossref. Not read (title and venue only).
DiLuna2025Byzantine
Giuseppe Antonio Di Luna, Paola Flocchini, Debasish Pattanayak, Giuseppe Prencipe, Francesco Piselli, Nicola Santoro (2025). Exploring Dangerous Graphs with Byzantine Companions. ICDCS 2025, pp. 352–361.
DiLuna2025DynamicBHS
Giuseppe Antonio Di Luna, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro (2025). Locating a black hole in a dynamic ring. Journal of Parallel and Distributed Computing 196:104998 (ICDCS 2021).
Feletti2025Transparency
Caterina Feletti, Lucia Mambretti, Carlo Mereghetti, Beatrice Palano (2025). Computational power of autonomous robots: Transparency vs. opaqueness. Theoretical Computer Science 1036:115153.
Georgiou2025Polygons
Konstantinos Georgiou, Caleb Jones, Jesse Lucier (2025). Multi-agent Search-Type Problems on Polygons. SOFSEM 2025, LNCS, pp. 314–332.
Georgiou2025Spirals
Konstantinos Georgiou, Caleb Jones, Matthew Madej (2025). Spirals and Beyond: Competitive Plane Search with Multi-Speed Agents. arXiv preprint.
Preprint, not peer reviewed.
Georgiou2025WeightedDisk
Konstantinos Georgiou, Xin Wang (2025). Weighted group search on the disk & improved lower bounds for priority evacuation. Journal of Computer and System Sciences 154:103678.
Conference version at IWOCA 2024, doi:10.1007/978-3-031-63021-7_3.
Himani2025TriangularGrids
Himani, Supantha Pandit (2025). Optimal Dispersion in Triangular Grids: Achieving Efficiency Without Prior Knowledge. ICDCIT 2025 (LNCS 15507).
doi:10.1007/978-3-031-81404-4_7
cited in grid
Jawhar2025Asymmetric
Khaled Jawhar, Evangelos Kranakis (2025). Bike-assisted evacuation of robots on a line with asymmetric S/R communication. Theoretical Computer Science 1053:115438.
Kamei2025Rings
Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil, Koichi Wada (2025). Gathering on rings for myopic asynchronous robots with lights. Theory of Computing Systems 69(1):8 (OPODIS 2019, LIPIcs 153, 27:1–27:17).
Metadata from Crossref and DataCite (OPODIS version doi 10.4230/LIPIcs.OPODIS.2019.27). OPODIS version in papers/; abstract read.
Kitamura2025TwoRobot
Naoki Kitamura, Yuichi Sudo, Koichi Wada (2025). Two-Robot Computational Landscape: A Complete Characterization of Model Power in Minimal Mobile Robot Systems. arXiv preprint.
Preprint, not peer reviewed.
Kshemkalyani2025Almost
Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, Debasish Pattanayak, Gokarna Sharma (2025). Dispersion is (Almost) Optimal under (A)synchrony. SPAA 2025.
Kshemkalyani2025AsyncTCS
Ajay D. Kshemkalyani (2025). Dispersion of mobile robots on graphs in the asynchronous model. Theoretical Computer Science 1044:115272.
Journal treatment (submitted 2019) of the asynchronous algorithms of Kshemkalyani & Ali 2019; no knowledge of \(n, m, D, \Delta, k\) needed.
Kshemkalyani2025NearLinear
Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, Gokarna Sharma (2025). Near-Linear Time Leader Election in Multiagent Networks. AAMAS 2025, pp. 1218–1226.
doi:10.65109/BKZJ3357
cited in no-knowledge
Mondal2025DkDDynamicRing
Brati Mondal, Pritam Goswami, Buddhadeb Sau (2025). Time Optimal Distance-k-Dispersion on Dynamic Ring. ICDCN 2025.
Distance-\(k\)-dispersion with \(k = 1\) is dispersion.
Mondal2025SimulatingChirality
Brati Mondal, Pritam Goswami, Buddhadeb Sau (2025). Simulating Chirality: Solving Distance-k-Dispersion on an 1-Interval Connected Ring. arXiv preprint.
arXiv:2507.14723
cited in dynamic-ring
Naito2025Beyond
Shota Naito, Tsukasa Ninomiya, Koichi Wada (2025). Beyond Pairwise Comparisons: Unveiling Structural Landscape of Mobile Robot Models. SSS 2025, LNCS, pp. 408–424.
Ooshita2024Crash
Fukuhito Ooshita, Naoki Kitamura, Ryota Eguchi, Michiko Inoue, Hirotsugu Kakugawa, Sayaka Kamei, Masahiro Shibata, Yuichi Sudo (2025). Crash-tolerant perpetual exploration with myopic luminous robots on rings. OPODIS 2024 (LIPIcs 324), 12:1–12:16.
doi:10.4230/LIPIcs.OPODIS.2024.12
cited in ring-async-perpetual-phi2, ring-fsync-perpetual-crash, ring-async-perpetual-crash, ring-async-perpetual-crash-phi2
Metadata from DataCite. Checked against the full text (open access): abstract, contribution and Table 1.
Ooshita2025Colors
Fukuhito Ooshita, Hirotsugu Kakugawa, Sayaka Kamei, Masahiro Shibata (2025). Crash-tolerant perpetual exploration of myopic luminous robots with fewer colors on rings. CANDAR Workshops 2025, pp. 166–172.
Metadata from Crossref. A copy is in papers/; abstract and Table I read, proofs not checked.
Padalkin2025Joint
Andreas Padalkin, Manish Kumar, Christian Scheideler (2025). Reconfiguration and locomotion with joint movements in the amoebot model. Autonomous Robots 49.
Pattanayak2025OptimalAsync
Debasish Pattanayak, Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, Gokarna Sharma (2025). Brief Announcement: Optimal Dispersion Under Asynchrony. DISC 2025, brief announcement (LIPIcs 356); journal version: Full version: Asynchronous Dispersion with Optimal Time Complexity, ICPP 2026 (doi:10.1145/3832810.3832921); brief announcement also at SPAA 2026 (doi:10.1145/3816782.3819188).
Pramanick2025Mobility
Subhajit Pramanick, Saswata Jana, Partha Sarathi Mandal, Gokarna Sharma (2025). Asynchronous Gathering of Opaque Robots with Mobility Faults. arXiv preprint.
Preprint, not peer reviewed.
Saxena2025Balanced
Ashish Saxena, Tanvir Kaur, Kaushik Mondal (2025). Dispersion on Time Varying Graphs. ICDCN 2025; journal version: Balanced dispersion on time-varying dynamic graphs, Journal of Computer and System Sciences 161:103829, 2026 (doi:10.1016/j.jcss.2026.103829).
Saxena2025PathConnected
Ashish Saxena, Kaushik Mondal (2025). Path Connected Dynamic Graphs with a Study of Efficient Dispersion. ICDCN 2025; journal version: Theoretical Computer Science 1050:115390, 2025 (doi:10.1016/j.tcs.2025.115390).
Sharma2025Discrete
Avisek Sharma, Pritam Goswami, Buddhadeb Sau (2025). Computational Power of Mobile Robots: Discrete Version. ICDCN 2025, pp. 231–238.
Bramas2026AsyncGrid
Quentin Bramas, Stéphane Devismes, Anaïs Durand, Pascal Lafourcade, Anissa Lamani (2026). Optimal asynchronous perpetual finite grid exploration. Theoretical Computer Science 1082:116072 (SSS 2024, LNCS, pp. 89–105, as “Optimal Asynchronous Perpetual Grid Exploration”).
doi:10.1016/j.tcs.2026.116072link
cited in grid-async-perpetual-chirality, grid-async-perpetual-chirality-phi2, grid-async-perpetual-phi2, grid-async-perpetual-phi3
Metadata from Crossref (SSS 2024 version doi 10.1007/978-3-031-74498-3_6). Checked against the SSS 2024 version on HAL: abstract, Table 1, model, Theorems 2–3, conclusion; the journal version was not read.
Bramas2026Grey
Quentin Bramas, Stéphane Devismes, Anaïs Durand, Pascal Lafourcade, Anissa Lamani (2026). 77 shades of grey. Preprint, HAL hal-05504522.
Metadata from the HAL record; not peer reviewed as far as found. A copy is in papers/; abstract read.
Bramas2026StandUp
Quentin Bramas, Hirotsugu Kakugawa, Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Masahiro Shibata, Sébastien Tixeuil (2026). Stand-up indulgent gathering on lines for myopic luminous robots. The Computer Journal 69(7):1122–1132.
Metadata from Crossref. arXiv version in papers/; abstract read.
Chalopin2026Holes
Jérémie Chalopin, Shantanu Das, Maria Kokkou (2026). Silent Self-stabilising Leader Election in Programmable Matter Systems with Holes. SIROCCO 2026, LNCS, pp. 151–171.
Chalopin2026Stationary
Jérémie Chalopin, Shantanu Das, Maria Kokkou (2026). Deterministic leader election for stationary programmable matter with common direction. Theoretical Computer Science 1080:116045.
Conference version at SIROCCO 2024, LNCS, pp. 174–191, doi:10.1007/978-3-031-60603-8_10.
Chand2026MDS
Prabhat Kumar Chand, Anisur Rahaman Molla (2026). Improved Linear-Time Construction of Minimal Dominating Set via Mobile Agents. ICDCIT 2026, pp. 35–51.
Chand2026Triangle
Prabhat Kumar Chand, Apurba Das, Anisur Rahaman Molla (2026). Agent-Based Triangle Counting: Unlocking Truss Decomposition, Triangle Centrality, and Local Clustering Coefficient. IEEE Transactions on Networking (2026).
Bounds are not in the abstract; not recorded here.
Coleman2026Plane
Jared Coleman, Evangelos Kranakis, Danny Krizanc, Oscar Morales-Ponce (2026). Search and Rescue on the Plane. arXiv preprint.
Preprint, not peer reviewed.
Cosson2026Polylog
Romain Cosson, Laurent Massoulié (2026). Polylogarithmic collective tree exploration. arXiv preprint (September 2026).
arXiv:2609.26789
cited in tree-global, tree-async-global
Preprint, not yet peer-reviewed; the paper carries an AI-assistance disclosure.
Devismes2026Homonymous
Stéphane Devismes, Yoann Dieudonné, Arnaud Labourel (2026). Can Like Attract Like? A Study of Homonymous Gathering in Networks. STOC 2026, pp. 933–942.
Feletti2026Dancing
Caterina Feletti, Paola Flocchini, Debasish Pattanayak, Giuseppe Prencipe, Nicola Santoro (2026). Universal Dancing by Luminous Robots Under Sequential Schedulers. SIROCCO 2026, pp. 292–312.
Flocchini2026Universal
Paola Flocchini, Alfredo Navarra, Debasish Pattanayak, Francesco Piselli, Nicola Santoro (2026). Universal pattern formation by oblivious robots under sequential schedulers. Distributed Computing (2026) (SIROCCO 2025).
Georgiou2026Fermat
Konstantinos Georgiou (2026). Optimal Average Disk-Inspection via Fermat’s Principle. LIPIcs, Volume 364, STACS 2026 44:1.
Georgiou2026Triangle
Konstantinos Georgiou, Woojin Jang (2026). Triangle evacuation of 2 agents in the wireless model & the power of choosing a starting point. Journal of Computer and System Sciences 155:103695.
Conference version at ALGOWIN 2022.
Hiraoka2026Block
Shoma Hiraoka, Shunsuke Imori, Shota Takahashi, Yuichi Sudo (2026). Color Complexity of Recolorable Graph Exploration: Upper and Lower Bounds via Block Structure. arXiv preprint 2609.14356.
Metadata from arXiv. Not peer reviewed. Checked against the full text (v1): model (Section 2), Theorems 3, 6, 11, 13, Lemma 4 and Table 1. The four-colour lower bound is computer-assisted (SAT certificate checked with DRAT).
Kaminski2026Circles
Bogumil Kaminski, Pawel Pralat, Maria Sadza (2026). Going in Circles: Collaborative Multi-Robot Treasure Hunting. arXiv preprint.
Preprint, not peer reviewed.
Kaur2026Dynamic
Tanvir Kaur, Ashish Saxena, Partha Sarathi Mandal, Kaushik Mondal (2026). Black hole search in dynamic graphs. Theoretical Computer Science 1086:116237 (ICDCN 2025).
Kaur2026MIS
Tanvir Kaur, Barun Gorain, Kaushik Mondal (2026). Maximal Independent Set via Leader Election by Mobile Agents from Arbitrary Initial Configuration Without Global Knowledge. SN Computer Science 7, article 125.
Bounds are those of the arXiv version; whether the journal article is its final version was not checked.
Kshemkalyani2026Leader
Ajay D. Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, Debasish Pattanayak, Gokarna Sharma (2026). Faster leader election via mobile agents and its applications. Theoretical Computer Science 1059:115578.
Masuzawa2026Disorientation
Toshimitsu Masuzawa, Yuichi Sudo, Koichi Wada (2026). Rendezvous under Variable Disorientation: The Algorithmic Power of Fixed Unit Distance. arXiv preprint.
arXiv:2610.09713
cited in two-fcom-rigid, two-fsta-rigid
Preprint, not peer reviewed.
Otaka2026TwoState
Kohei Otaka, Fabian Frei, Koichi Wada (2026). Gathering semi-synchronously scheduled two-state robots. Theoretical Computer Science 1068:115776.
doi:10.1016/j.tcs.2026.115776arXiv:2408.09999
cited in two-fcom-ssync, two-fcom, two-fcom-rigid, two-fsta, two-fsta-rigid, two-fsta-async, fcom-ssync, fsta-ssync
Conference version at SSS 2024, doi:10.1007/978-3-031-74498-3_15.
Pyati2026Separation
Prajyot Pyati, Navjot Kaur, Saswata Jana, Adri Bhattacharya, Partha Sarathi Mandal (2026). Separation of Unconscious Robots with Obstructed Visibility. ICDCIT 2026, pp. 68–84.
doi:10.1007/978-3-032-16632-6_5
cited in opaque
Saxena2026Highly
Ashish Saxena, Kaushik Mondal (2026). Exploration on highly dynamic graphs. Distributed Computing 39 (2026).
Sudo2026SelfStabilizing
Yuichi Sudo, Fukuhito Ooshita, Sayaka Kamei (2026). Self-stabilizing graph exploration by a single agent. Theoretical Computer Science 1082:116085.
Metadata from Crossref and arXiv (first version 2020; brief announcement at DISC 2024). Not read; the arXiv abstracts of different versions state different bounds.
Takahashi2025Recolorable
Shota Takahashi, Haruki Kanaya, Shoma Hiraoka, Ryota Eguchi, Yuichi Sudo (2026). Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors. OPODIS 2025 (LIPIcs 361), 32:1–32:15.
Metadata from DataCite and arXiv. Checked against the full text of arXiv v2 (September 2026): model (Section 2), Theorems 1–3, Note 1 and the conclusion. The LIPIcs abstract states the six-colour and φ-free five-colour results; the triangle-free five-colour result and Note 1 are in arXiv v2.