{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:22Z","timestamp":1760202622915},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2011,5,3]],"date-time":"2011-05-03T00:00:00Z","timestamp":1304380800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,6]]},"DOI":"10.1007\/s00453-011-9518-1","type":"journal-article","created":{"date-parts":[[2011,5,2]],"date-time":"2011-05-02T15:36:51Z","timestamp":1304350611000},"page":"26-38","source":"Crossref","is-referenced-by-count":15,"title":["Graph Decomposition for Memoryless Periodic Exploration"],"prefix":"10.1007","volume":"63","author":[{"given":"Adrian","family":"Kosowski","sequence":"first","affiliation":[]},{"given":"Alfredo","family":"Navarra","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2011,5,3]]},"reference":[{"key":"9518_CR1","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/mana.19780860120","volume":"86","author":"L. Budach","year":"1978","unstructured":"Budach, L.: Automata and labyrinths. Math. Nachr. 86, 195\u2013282 (1978)","journal-title":"Math. Nachr."},{"issue":"4","key":"9518_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1383369.1383373","volume":"4","author":"R. Cohen","year":"2008","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. ACM Trans. Algorithms 4(4), 1\u201318 (2008)","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"9518_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00453-007-9089-3","volume":"53","author":"R. Cohen","year":"2009","unstructured":"Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Labeling schemes for tree representation. Algorithmica 53(1), 1\u201315 (2009)","journal-title":"Algorithmica"},{"issue":"3","key":"9518_CR4","doi-asserted-by":"crossref","first-page":"636","DOI":"10.1137\/0209048","volume":"9","author":"S. Cook","year":"1980","unstructured":"Cook, S., Rackoff, C.: Space lower bounds for maze threadability on restricted machines. SIAM J. Comput. 9(3), 636\u2013652 (1980)","journal-title":"SIAM J. Comput."},{"key":"9518_CR5","series-title":"LNCS","first-page":"167","volume-title":"Proceedings of the 16th Colloquium on Structural Information and Communication Complexity (SIROCCO)","author":"J. Czyzowicz","year":"2009","unstructured":"Czyzowicz, J., Dobrev, S., G\u0105sieniec, L., Ilcinkas, D., Jansson, J., Klasing, R., Lignos, Y., Martin, R.A., Sadakane, K., Sung, W.K.: More efficient periodic traversal in anonymous undirected graphs. In: Proceedings of the 16th Colloquium on Structural Information and Communication Complexity (SIROCCO). LNCS, vol. 5869, pp. 167\u2013181 (2009)"},{"key":"9518_CR6","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/11429647_12","volume-title":"Proceedings of the 12th Colloquium on Structural Information and Communication Complexity (SIROCCO)","author":"S. Dobrev","year":"2005","unstructured":"Dobrev, S., Jansson, J., Sadakane, K., Sung, W.K.: Finding short right-hand-on-the-wall walks in graphs. In: Proceedings of the 12th Colloquium on Structural Information and Communication Complexity (SIROCCO). LNCS, vol. 3499, pp. 127\u2013139 (2005)"},{"issue":"2\u20133","key":"9518_CR7","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1016\/j.tcs.2005.07.014","volume":"345","author":"P. Fraigniaud","year":"2005","unstructured":"Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theor. Comput. Sci. 345(2\u20133), 331\u2013344 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"12","key":"9518_CR8","doi-asserted-by":"crossref","first-page":"2310","DOI":"10.1016\/j.dam.2007.11.001","volume":"156","author":"P. Fraigniaud","year":"2008","unstructured":"Fraigniaud, P., Ilcinkas, D., Pelc, A.: Impact of memory size on graph exploration capability. Discrete Appl. Math. 156(12), 2310\u20132319 (2008)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"9518_CR9","doi-asserted-by":"crossref","first-page":"802","DOI":"10.1016\/j.jcss.2007.09.004","volume":"74","author":"L. G\u0105sieniec","year":"2008","unstructured":"G\u0105sieniec, L., Klasing, R., Martin, R.A., Navarra, A., Zhang, X.: Fast periodic graph exploration with constant memory. J. Comput. Syst. Sci. 74(5), 802\u2013822 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"9518_CR10","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/978-3-540-92248-3_2","volume-title":"Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)","author":"L. G\u0105sieniec","year":"2008","unstructured":"G\u0105sieniec, L., Radzik, T.: Memory efficient anonymous graph exploration. In: Proceedings of the 34th International Workshop on Graph-Theoretic Concepts in Computer Science (WG). LNCS, vol. 5344, pp. 14\u201329 (2008)"},{"issue":"1\u20133","key":"9518_CR11","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1016\/j.tcs.2008.03.035","volume":"401","author":"D. Ilcinkas","year":"2008","unstructured":"Ilcinkas, D.: Setting port numbers for fast graph exploration. Theor. Comput. Sci. 401(1\u20133), 236\u2013242 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"9518_CR12","series-title":"LNCS","first-page":"501","volume-title":"Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS)","author":"A. Kosowski","year":"2009","unstructured":"Kosowski, A., Navarra, A.: Graph decomposition for improving memoryless periodic exploration. In: Proceedings of the 34th International Symposium on Mathematical Foundations of Computer Science (MFCS). LNCS, vol. 5734, pp. 501\u2013512 (2009)"},{"key":"9518_CR13","first-page":"376","volume-title":"Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC)","author":"O. Reingold","year":"2005","unstructured":"Reingold, O.: Undirected st-connectivity in log-space. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC), pp. 376\u2013385 (2005)"},{"key":"9518_CR14","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/BF00288647","volume":"13","author":"H. Rollik","year":"1980","unstructured":"Rollik, H.: Automaten in planaren graphen. Acta Inform. 13, 287\u2013298 (1980)","journal-title":"Acta Inform."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9518-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9518-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9518-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:07Z","timestamp":1559123107000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9518-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,3]]},"references-count":14,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2012,6]]}},"alternative-id":["9518"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9518-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,3]]}}}