{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T13:17:45Z","timestamp":1753881465574,"version":"3.41.2"},"reference-count":23,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","funder":[{"name":"Leverhulme Research Centre"},{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/P02002X\/1"],"award-info":[{"award-number":["EP\/P02002X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Parallel Process. Lett."],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:p> We examine the problem of gathering [Formula: see text] agents (or multi-agent rendezvous) in dynamic graphs which may change in every round. We consider a variant of the [Formula: see text]-interval connectivity model [9] in which all instances (snapshots) are always connected spanning subgraphs of an underlying graph, not necessarily a clique. The agents are identical and not equipped with explicit communication capabilities, and are initially arbitrarily positioned on the graph. The problem is for the agents to gather at the same node, not fixed in advance. We first show that the problem becomes impossible to solve if the underlying graph has a cycle. In light of this, we study a relaxed version of this problem, called weak gathering, where the agents are allowed to gather either at the same node, or at two adjacent nodes. Our goal is to characterize the class of 1-interval connected graphs and initial configurations in which the problem is solvable, both with and without homebases. On the negative side we show that when the underlying graph contains a spanning bicyclic subgraph and satisfies an additional connectivity property, weak gathering is unsolvable, thus we concentrate mainly on unicyclic graphs. As we show, in most instances of initial agent configurations, the agents must meet on the cycle. This adds an additional difficulty to the problem, as they need to explore the graph and recognize the nodes that form the cycle. We provide a deterministic algorithm for the solvable cases of this problem that runs in [Formula: see text] number of rounds. <\/jats:p>","DOI":"10.1142\/s0129626421500201","type":"journal-article","created":{"date-parts":[[2021,11,10]],"date-time":"2021-11-10T11:47:33Z","timestamp":1636544853000},"source":"Crossref","is-referenced-by-count":0,"title":["Beyond Rings: Gathering in 1-Interval Connected Graphs"],"prefix":"10.1142","volume":"31","author":[{"given":"Othon","family":"Michail","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Liverpool, UK"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, UK"},{"name":"Computer Engineering and Informatics Department, University of Patras, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3699-0179","authenticated-orcid":false,"given":"Michail","family":"Theofilatos","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Liverpool, UK"}]}],"member":"219","published-online":{"date-parts":[[2021,11,11]]},"reference":[{"issue":"4","key":"S0129626421500201BIB001","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2344422.2344427","volume":"8","author":"Czyzowicz J.","year":"2012","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"S0129626421500201BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.12.016"},{"key":"S0129626421500201BIB003","first-page":"184","volume-title":"European Symposium on Algorithms","author":"Dessmark A.","year":"2003"},{"key":"S0129626421500201BIB004","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1016\/j.tcs.2020.04.002","volume":"822","author":"Shibata M.","year":"2020","journal-title":"Theoretical Computer Science"},{"key":"S0129626421500201BIB005","first-page":"234","volume-title":"International Conference on Current Trends in Theory and Practice of Computer Science","author":"Czyzowicz J.","year":"2008"},{"key":"S0129626421500201BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1223-5"},{"key":"S0129626421500201BIB007","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/978-3-540-75142-7_11","volume-title":"International Symposium on Distributed Computing","author":"Chalopin J.","year":"2007"},{"key":"S0129626421500201BIB008","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/j.tcs.2018.10.018","volume":"811","author":"Di\u00a0Luna G. A.","year":"2020","journal-title":"Theoretical Computer Science"},{"key":"S0129626421500201BIB009","first-page":"513","volume-title":"Proceedings of the 42nd ACM symposium on Theory of Computing (STOC)","author":"Kuhn F.","year":"2010"},{"key":"S0129626421500201BIB010","first-page":"570","volume-title":"36th International Conference on Distributed Computing Systems (ICDCS)","author":"Di\u00a0Luna G. A.","year":"2016"},{"volume-title":"24th International Conference on Principles of Distributed Systems (OPODIS\u00a02020)","year":"2021","author":"Das S.","key":"S0129626421500201BIB011"},{"key":"S0129626421500201BIB012","first-page":"775","volume-title":"38th International Conference on Distributed Computing Systems (ICDCS)","author":"Gotoh T.","year":"2018"},{"volume-title":"23rd International Conference on Principles of Distributed Systems (OPODIS\u00a02019)","year":"2020","author":"Gotoh T.","key":"S0129626421500201BIB013"},{"key":"S0129626421500201BIB014","doi-asserted-by":"publisher","DOI":"10.2200\/S00278ED1V01Y201004DCT001"},{"issue":"3","key":"S0129626421500201BIB015","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1002\/net.21453","volume":"59","author":"Pelc A.","year":"2012","journal-title":"Networks"},{"issue":"1","key":"S0129626421500201BIB016","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/s00453-006-0074-2","volume":"46","author":"Dessmark A.","year":"2006","journal-title":"Algorithmica"},{"issue":"109","key":"S0129626421500201BIB017","volume":"1","author":"Das S.","year":"2013","journal-title":"Bulletin of EATCS"},{"key":"S0129626421500201BIB018","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/11429647_10","volume-title":"International Colloquium on Structural Information and Communication Complexity","author":"Das S.","year":"2005"},{"issue":"1","key":"S0129626421500201BIB019","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1016\/j.tcs.2007.05.011","volume":"385","author":"Das S.","year":"2007","journal-title":"Theoretical Computer Science"},{"key":"S0129626421500201BIB020","first-page":"1278","volume-title":"International Conference on Robotics and Automation","author":"Gong C.","year":"2012"},{"key":"S0129626421500201BIB021","first-page":"316","volume-title":"Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Panaite P.","year":"1998"},{"key":"S0129626421500201BIB022","doi-asserted-by":"publisher","DOI":"10.1080\/17445760.2012.668546"},{"issue":"1","key":"S0129626421500201BIB023","doi-asserted-by":"crossref","first-page":"2016","DOI":"10.1016\/j.jpdc.2013.07.007","volume":"74","author":"Michail O.","year":"2014","journal-title":"Journal of Parallel and Distributed Computing"}],"container-title":["Parallel Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129626421500201","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,23]],"date-time":"2021-12-23T09:46:36Z","timestamp":1640252796000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129626421500201"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,11]]},"references-count":23,"journal-issue":{"issue":"04","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["10.1142\/S0129626421500201"],"URL":"https:\/\/doi.org\/10.1142\/s0129626421500201","relation":{},"ISSN":["0129-6264","1793-642X"],"issn-type":[{"type":"print","value":"0129-6264"},{"type":"electronic","value":"1793-642X"}],"subject":[],"published":{"date-parts":[[2021,11,11]]},"article-number":"2150020"}}