{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T15:10:08Z","timestamp":1756307408276,"version":"3.44.0"},"reference-count":23,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2025,9,1]],"date-time":"2025-09-01T00:00:00Z","timestamp":1756684800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100007052","name":"University of Verona","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007052","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2025,9]]},"DOI":"10.1016\/j.ic.2025.105334","type":"journal-article","created":{"date-parts":[[2025,8,11]],"date-time":"2025-08-11T23:20:46Z","timestamp":1754954446000},"page":"105334","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Linear-time safe-alternating DFS and SCCs"],"prefix":"10.1016","volume":"306","author":[{"ORCID":"https:\/\/2.zoppoz.workers.dev:443\/https\/orcid.org\/0000-0001-5748-2029","authenticated-orcid":false,"given":"Carlo","family":"Comin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/j.ic.2025.105334_br0010","series-title":"Algorithms and Computation: 12th International Symposium, ISAAC 2001 Christchurch, New Zealand, December 19\u201321, 2001 Proceedings","first-page":"550","author":"Bodlaender","year":"2001"},{"issue":"4","key":"10.1016\/j.ic.2025.105334_br0020","doi-asserted-by":"crossref","first-page":"1533","DOI":"10.1137\/070693217","article-title":"Linear-time algorithms for dominators and other path-evaluation problems","volume":"38","author":"Buchsbaum","year":"2008","journal-title":"SIAM J. Comput."},{"issue":"1","key":"10.1016\/j.ic.2025.105334_br0030","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","article-title":"Alternation","volume":"28","author":"Chandra","year":"1981","journal-title":"J. ACM"},{"key":"10.1016\/j.ic.2025.105334_br0040","series-title":"FOCS","first-page":"98","article-title":"Alternation","author":"Chandra","year":"1976"},{"key":"10.1016\/j.ic.2025.105334_br0050","series-title":"30th International Conference on Concurrency Theory, CONCUR 2019, August 27-30, 2019, Amsterdam, the Netherlands","first-page":"7:1","article-title":"Near-linear time algorithms for streett objectives in graphs and mdps","volume":"vol. 140","author":"Chatterjee","year":"2019"},{"key":"10.1016\/j.ic.2025.105334_br0060","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/2597631","article-title":"Efficient and dynamic algorithms for alternating B\u00fcchi games and maximal end-component decomposition","volume":"61","author":"Chatterjee","year":"2014","journal-title":"J. ACM"},{"key":"10.1016\/j.ic.2025.105334_br0070","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/BF01940880","article-title":"Algorithms for dense graphs and networks on the random access computer","volume":"15","author":"Cheriyan","year":"061996","journal-title":"Algorithmica"},{"year":"2001","series-title":"Introduction to Algorithms","author":"Cormen","key":"10.1016\/j.ic.2025.105334_br0080"},{"issue":"4","key":"10.1016\/j.ic.2025.105334_br0090","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1145\/210332.210339","article-title":"The complexity of probabilistic verification","volume":"42","author":"Courcoubetis","year":"1995","journal-title":"J. ACM"},{"year":"1976","series-title":"A Discipline of Programming, Ch. 25","author":"Dijkstra","key":"10.1016\/j.ic.2025.105334_br0100"},{"key":"10.1016\/j.ic.2025.105334_br0110","series-title":"Proceedings of the 10th Australasian Workshop on Combinatorial Algorithms","first-page":"7","article-title":"Update games and update networks","author":"Dinneen","year":"1999"},{"key":"10.1016\/j.ic.2025.105334_br0120","series-title":"Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000 Konstanz, Germany, June 15\u201317, 2000 Proceedings","first-page":"127","author":"Dinneen","year":"2000"},{"issue":"3","key":"10.1016\/j.ic.2025.105334_br0130","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0020-0190(00)00051-X","article-title":"Path-based depth-first search for strong and biconnected components","volume":"74","author":"Gabow","year":"2000","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"10.1016\/j.ic.2025.105334_br0140","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/0022-0000(85)90014-5","article-title":"A linear-time algorithm for a special case of disjoint set union","volume":"30","author":"Gabow","year":"1985","journal-title":"J. Comput. Syst. Sci."},{"year":"2002","series-title":"Automata Logics, and Infinite Games: A Guide to Current Research","key":"10.1016\/j.ic.2025.105334_br0150"},{"year":"1995","series-title":"Limits to Parallel Computation: P-Completeness Theory","author":"Greenlaw","key":"10.1016\/j.ic.2025.105334_br0160"},{"key":"10.1016\/j.ic.2025.105334_br0170","series-title":"IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2008, December 9-11, 2008","first-page":"235","article-title":"Explicit M\u00fcller games are PTIME","author":"Horn","year":"2008"},{"key":"10.1016\/j.ic.2025.105334_br0180","series-title":"FOCS","first-page":"89","article-title":"On parallelism in Turing machines","author":"Kozen","year":"1976"},{"issue":"2","key":"10.1016\/j.ic.2025.105334_br0190","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","article-title":"Relationships between nondeterministic and deterministic tape complexities","volume":"4","author":"Savitch","year":"1970","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10.1016\/j.ic.2025.105334_br0200","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0898-1221(81)90008-0","article-title":"A strong-connectivity algorithm and its applications in data flow analysis","volume":"7","author":"Sharir","year":"1981","journal-title":"Comput. Math. Appl."},{"issue":"2","key":"10.1016\/j.ic.2025.105334_br0210","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."},{"issue":"2","key":"10.1016\/j.ic.2025.105334_br0220","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1145\/321879.321884","article-title":"Efficiency of a good but not linear set union algorithm","volume":"22","author":"Tarjan","year":"1975","journal-title":"J. ACM"},{"key":"10.1016\/j.ic.2025.105334_br0230","doi-asserted-by":"crossref","DOI":"10.1016\/j.ejc.2023.103815","article-title":"Finding strong components using depth-first search","volume":"119","author":"Tarjan","year":"2024","journal-title":"Eur. J. Comb."}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S0890540125000707?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.elsevier.com\/content\/article\/PII:S0890540125000707?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T14:43:13Z","timestamp":1756305793000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/linkinghub.elsevier.com\/retrieve\/pii\/S0890540125000707"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9]]},"references-count":23,"alternative-id":["S0890540125000707"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.ic.2025.105334","relation":{},"ISSN":["0890-5401"],"issn-type":[{"type":"print","value":"0890-5401"}],"subject":[],"published":{"date-parts":[[2025,9]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Linear-time safe-alternating DFS and SCCs","name":"articletitle","label":"Article Title"},{"value":"Information and Computation","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1016\/j.ic.2025.105334","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2025 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"105334"}}