{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T23:42:05Z","timestamp":1776123725955,"version":"3.50.1"},"reference-count":44,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2028,3,27]],"date-time":"2028-03-27T00:00:00Z","timestamp":1837728000000},"content-version":"am","delay-in-days":696,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:00:00Z","timestamp":1777593600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJFR226U"],"award-info":[{"award-number":["JPMJFR226U"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP19K11826"],"award-info":[{"award-number":["JP19K11826"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP20KK0232"],"award-info":[{"award-number":["JP20KK0232"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2026,5]]},"DOI":"10.1016\/j.tcs.2026.115908","type":"journal-article","created":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T08:36:47Z","timestamp":1773909407000},"page":"115908","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Complete graph identification in population protocols"],"prefix":"10.1016","volume":"1073","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-8102-0280","authenticated-orcid":false,"given":"Haruki","family":"Kanaya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4442-1750","authenticated-orcid":false,"given":"Yuichi","family":"Sudo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"issue":"4","key":"10.1016\/j.tcs.2026.115908_bib0001","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/s00446-005-0138-3","article-title":"Computation in networks of passively mobile finite-state sensors","volume":"18","author":"Angluin","year":"2006","journal-title":"Distrib. Comput."},{"key":"10.1016\/j.tcs.2026.115908_bib0002","series-title":"Distributed Computing in Sensor Systems","first-page":"63","article-title":"Stably computable properties of network graphs","author":"Angluin","year":"2005"},{"key":"10.1016\/j.tcs.2026.115908_bib0003","series-title":"25th International Conference on Principles of Distributed Systems (OPODIS 2021)","first-page":"13:1","article-title":"Population protocols for graph class identification problems","author":"Yasumi","year":"2022"},{"issue":"4","key":"10.1016\/j.tcs.2026.115908_bib0004","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/s00446-016-0281-z","article-title":"Stable leader election in population protocols requires linear time","volume":"31","author":"Doty","year":"2018","journal-title":"Distrib. Comput."},{"issue":"2","key":"10.1016\/j.tcs.2026.115908_bib0005","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s00446-020-00385-0","article-title":"Time-space trade-offs in population protocols for the majority problem","volume":"34","author":"Berenbrink","year":"2021","journal-title":"Distrib. Comput."},{"key":"10.1016\/j.tcs.2026.115908_bib0006","series-title":"Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing","first-page":"34","article-title":"Efficient size estimation and impossibility of termination in uniform dense population protocols","author":"Doty","year":"2019"},{"key":"10.1016\/j.tcs.2026.115908_bib0007","series-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"2221","article-title":"Space-Optimal majority in population protocols","author":"Alistarh","year":"2018"},{"key":"10.1016\/j.tcs.2026.115908_bib0008","series-title":"Automata, Languages, and Programming","first-page":"479","article-title":"Polylogarithmic-Time leader election in population protocols","author":"Alistarh","year":"2015"},{"issue":"3","key":"10.1016\/j.tcs.2026.115908_bib0009","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/s00446-008-0067-z","article-title":"Fast computation by population protocols with a leader","volume":"21","author":"Angluin","year":"2008","journal-title":"Distrib. Comput."},{"key":"10.1016\/j.tcs.2026.115908_bib0010","series-title":"Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing","first-page":"119","article-title":"Optimal time and space leader election in population protocols","author":"Berenbrink","year":"2020"},{"key":"10.1016\/j.tcs.2026.115908_bib0011","series-title":"Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"265","article-title":"Fast space optimal leader election in population protocols","author":"G\u0105sieniec","year":"2018"},{"key":"10.1016\/j.tcs.2026.115908_bib0012","series-title":"The 31St ACM Symposium on Parallelism in Algorithms and Architectures","first-page":"93","article-title":"Almost logarithmic-Time space optimal leader election in population protocols","author":"G\u0105sieniec","year":"2019"},{"issue":"A","key":"10.1016\/j.tcs.2026.115908_bib0013","article-title":"Simple and fast approximate counting and leader election in populations","volume":"285","author":"Michail","year":"2022","journal-title":"Inf. Comput."},{"issue":"01","key":"10.1016\/j.tcs.2026.115908_bib0014","doi-asserted-by":"crossref","DOI":"10.1142\/S012962642050005X","article-title":"Leader election requires logarithmic time in population protocols","volume":"30","author":"Sudo","year":"2020","journal-title":"Parallel Process. Lett."},{"issue":"11","key":"10.1016\/j.tcs.2026.115908_bib0015","doi-asserted-by":"crossref","first-page":"2620","DOI":"10.1109\/TPDS.2020.2991771","article-title":"Time-Optimal leader election in population protocols","volume":"31","author":"Sudo","year":"2020","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"10.1016\/j.tcs.2026.115908_bib0016","series-title":"Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"2560","article-title":"Time-Space trade-offs in population protocols","author":"Alistarh","year":"2017"},{"key":"10.1016\/j.tcs.2026.115908_bib0017","series-title":"Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing","first-page":"47","article-title":"Fast and exact majority in population protocols","author":"Alistarh","year":"2015"},{"issue":"2","key":"10.1016\/j.tcs.2026.115908_bib0018","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s00446-008-0059-z","article-title":"A simple population protocol for fast robust approximate majority","volume":"21","author":"Angluin","year":"2008","journal-title":"Distrib. Comput."},{"key":"10.1016\/j.tcs.2026.115908_bib0019","series-title":"Proceedings of the 39th Symposium on Principles of Distributed Computing","first-page":"191","article-title":"An o(log3\/2 n) parallel time population protocol for majority with o(log n) states","author":"Ben-Nun","year":"2020"},{"key":"10.1016\/j.tcs.2026.115908_bib0020","series-title":"32nd International Symposium on Distributed Computing (DISC 2018)","first-page":"10:1","article-title":"A population protocol for exact majority with o(log5\/3 n) stabilization time and theta(log n) states","author":"Berenbrink","year":"2018"},{"key":"10.1016\/j.tcs.2026.115908_bib0021","series-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing","first-page":"451","article-title":"Brief announcement: population protocols for leader election and exact majority with o(log2 n) states and o(log2 n) convergence time","author":"Bilke","year":"2017"},{"key":"10.1016\/j.tcs.2026.115908_bib0022","series-title":"2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)","first-page":"1044","article-title":"A time and space optimal stable population protocol solving exact majority","author":"Doty","year":"2022"},{"issue":"1","key":"10.1016\/j.tcs.2026.115908_bib0023","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00446-016-0277-8","article-title":"Determining majority in networks with local interactions and very small local memory","volume":"30","author":"Mertzios","year":"2017","journal-title":"Distrib. Comput."},{"key":"10.1016\/j.tcs.2026.115908_bib0024","series-title":"2015 IEEE 14th International Symposium on Network Computing and Applications","first-page":"35","article-title":"Counting with population protocols","author":"Mocquard","year":"2015"},{"key":"10.1016\/j.tcs.2026.115908_bib0025","series-title":"2016 IEEE 15th International Symposium on Network Computing and Applications (NCA)","first-page":"216","article-title":"Optimal proportion computation with population protocols","author":"Mocquard","year":"2016"},{"key":"10.1016\/j.tcs.2026.115908_bib0026","series-title":"Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing","first-page":"292","article-title":"Stably computable predicates are semilinear","author":"Angluin","year":"2006"},{"issue":"4","key":"10.1016\/j.tcs.2026.115908_bib0027","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/s00446-007-0040-2","article-title":"The computational power of population protocols","volume":"20","author":"Angluin","year":"2007","journal-title":"Distrib. Comput."},{"key":"10.1016\/j.tcs.2026.115908_bib0028","series-title":"20th International Conference on Principles of Distributed Systems (OPODIS 2016)","first-page":"13:1","article-title":"Time and space optimal counting in population protocols","author":"Aspnes","year":"2017"},{"key":"10.1016\/j.tcs.2026.115908_bib0029","series-title":"Distrib. Comput. (DISC 2015)","first-page":"631","article-title":"Space-Optimal counting in population protocols","author":"Beauquier","year":"2015"},{"key":"10.1016\/j.tcs.2026.115908_bib0030","series-title":"25th International Conference on Principles of Distributed Systems (OPODIS 2021)","first-page":"14:1","article-title":"Fast graphical population protocols","author":"Alistarh","year":"2022"},{"key":"10.1016\/j.tcs.2026.115908_bib0031","series-title":"Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing","first-page":"246","article-title":"Near-Optimal leader election in population protocols on graphs","author":"Alistarh","year":"2022"},{"key":"10.1016\/j.tcs.2026.115908_bib0032","series-title":"Extended Abstracts Summer 2015","first-page":"77","article-title":"Population protocols for majority in arbitrary networks","author":"Mertzios","year":"2017"},{"key":"10.1016\/j.tcs.2026.115908_bib0033","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/j.tcs.2021.09.020","article-title":"Uniform bipartition in the population protocol model with arbitrary graphs","volume":"892","author":"Yasumi","year":"2021","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2026.115908_bib0034","series-title":"Principles of Distributed Systems","first-page":"38","article-title":"Self-stabilizing leader election in population protocols over arbitrary communication graphs","author":"Beauquier","year":"2013"},{"key":"10.1016\/j.tcs.2026.115908_bib0035","series-title":"Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing","first-page":"53","article-title":"Self-stabilizing leader election","author":"Chen","year":"2019"},{"key":"10.1016\/j.tcs.2026.115908_bib0036","series-title":"Proceedings of the 39th Symposium on Principles of Distributed Computing","first-page":"210","article-title":"Self-stabilizing leader election in regular graphs","author":"Chen","year":"2020"},{"key":"10.1016\/j.tcs.2026.115908_bib0037","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.tcs.2012.01.007","article-title":"Loosely-stabilizing leader election in a population protocol model","volume":"444","author":"Sudo","year":"2012","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10.1016\/j.tcs.2026.115908_bib0038","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1587\/transinf.2019FCP0003","article-title":"Loosely stabilizing leader election on arbitrary graphs in population protocols without identifiers or random numbers","volume":"E103.D","author":"Sudo","year":"2020","journal-title":"IEICE Trans. Inf. Syst."},{"issue":"12","key":"10.1016\/j.tcs.2026.115908_bib0039","doi-asserted-by":"crossref","first-page":"1675","DOI":"10.1587\/transfun.2020EAP1125","article-title":"Time-Optimal self-Stabilizing leader election on rings in population protocols","volume":"E104.A","author":"Yokota","year":"2021","journal-title":"IEICE Trans. Fundam. Elect., Commun. Comput. Sci."},{"key":"10.1016\/j.tcs.2026.115908_bib0040","series-title":"Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing","first-page":"2","article-title":"A near time-Optimal population protocol for self-Stabilizing leader election on rings with a poly-Logarithmic number of states","author":"Yokota","year":"2023"},{"issue":"4","key":"10.1016\/j.tcs.2026.115908_bib0041","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1452001.1452003","article-title":"Self-Stabilizing population protocols","volume":"3","author":"Angluin","year":"2008","journal-title":"ACM Trans. Auton. Adapt. Syst."},{"issue":"22","key":"10.1016\/j.tcs.2026.115908_bib0042","doi-asserted-by":"crossref","first-page":"2434","DOI":"10.1016\/j.tcs.2011.02.003","article-title":"Mediated population protocols","volume":"412","author":"Michail","year":"2011","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10.1016\/j.tcs.2026.115908_bib0043","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/s00446-015-0257-4","article-title":"Simple and efficient local codes for distributed stable network construction","volume":"29","author":"Michail","year":"2016","journal-title":"Distrib. Comput."},{"issue":"12","key":"10.1016\/j.tcs.2026.115908_bib0044","doi-asserted-by":"crossref","first-page":"3011","DOI":"10.1109\/TPDS.2021.3076769","article-title":"Self-Stabilizing population protocols with global knowledge","volume":"32","author":"Sudo","year":"2021","journal-title":"IEEE Trans. Parallel Distrib. Syst."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526001672?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397526001672?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T22:43:37Z","timestamp":1776120217000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397526001672"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":44,"alternative-id":["S0304397526001672"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115908","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2026,5]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Complete graph identification in population protocols","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2026.115908","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"115908"}}