{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:41Z","timestamp":1760202761542,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,3,1]],"date-time":"2018-03-01T00:00:00Z","timestamp":1519862400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s10878-018-0270-1","type":"journal-article","created":{"date-parts":[[2018,2,28]],"date-time":"2018-02-28T21:51:02Z","timestamp":1519854662000},"page":"465-481","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS"],"prefix":"10.1007","volume":"37","author":[{"given":"Sankardeep","family":"Chakraborty","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0636-9880","authenticated-orcid":false,"given":"Srinivasa Rao","family":"Satti","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,1]]},"reference":[{"key":"270_CR1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational complexity: a modern approach","author":"S Arora","year":"2009","unstructured":"Arora S, Barak B (2009) Computational complexity: a modern approach. Cambridge University Press, Cambridge"},{"issue":"3","key":"270_CR2","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1016\/j.comgeo.2013.11.004","volume":"47","author":"T Asano","year":"2014","unstructured":"Asano T, Buchin K, Buchin M, Korman M, Mulzer W, Rote G, Schulz A (2014) Reprint of: memory-constrained algorithms for simple polygons. Comput Geom 47(3):469\u2013479","journal-title":"Comput Geom"},{"key":"270_CR3","unstructured":"Asano T, Izumi T, Kiyomi M, Konagaya M, Ono H, Otachi Y, Schweitzer P, Tarui J, Uehara R (2014) Depth-first search using \n                    \n                      \n                    \n                    $$\\text{O}(n)$$\n                    \n                      \n                        \n                          O\n                          (\n                          n\n                          )\n                        \n                      \n                    \n                   bits. In: 25th ISAAC, pp. 553\u2013564"},{"key":"270_CR4","doi-asserted-by":"crossref","unstructured":"Banerjee N, Chakraborty S, Raman V (2016) Improved space efficient algorithms for BFS, DFS and applications. In: 22nd COCOON (LNCS), vol 9797. Springer, pp 119\u2013130","DOI":"10.1007\/978-3-319-42634-1_10"},{"key":"270_CR5","doi-asserted-by":"crossref","unstructured":"Banerjee N, Chakraborty S, Raman V, Roy S, Saurabh S (2015) Time-space tradeoffs for dynamic programming in trees and bounded treewidth graphs. In 21st COCOON (LNCS), vol 9198. Springer, pp 349\u2013360","DOI":"10.1007\/978-3-319-21398-9_28"},{"key":"270_CR6","doi-asserted-by":"crossref","unstructured":"Banerjee N, Chakraborty S, Raman V, Satti SR (2018) Space efficient linear time algorithms for BFS, DFS and applications. Theory Comput Syst","DOI":"10.1007\/s00224-017-9841-2"},{"issue":"5","key":"270_CR7","doi-asserted-by":"publisher","first-page":"1273","DOI":"10.1137\/S0097539793283151","volume":"27","author":"G Barnes","year":"1998","unstructured":"Barnes G, Buss J, Ruzzo W, Schieber B (1998) A sublinear space, polynomial time algorithm for directed s-t connectivity. SICOMP 27(5):1273\u20131282","journal-title":"SICOMP"},{"key":"270_CR8","unstructured":"Batagelj V, Zaversnik M (2003) An \n                    \n                      \n                    \n                    $$\\text{ O }(m)$$\n                    \n                      \n                        \n                          \n                          O\n                          \n                          (\n                          m\n                          )\n                        \n                      \n                    \n                   algorithm for cores decomposition of networks. CoRR. arXiv preprint cs.DS\/0310049"},{"issue":"1","key":"270_CR9","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1137\/070684355","volume":"23","author":"A Berry","year":"2009","unstructured":"Berry A, Krueger R, Simonet G (2009) Maximal label search algorithms to compute perfect and minimal elimination orderings. SIAM J Discrete Math 23(1):428\u2013446","journal-title":"SIAM J Discrete Math"},{"key":"270_CR10","unstructured":"Chakraborty S, Jo S, Satti SR (2017) Improved space-efficient linear time algorithms for some classical graph problems. In: 15th CTW"},{"key":"270_CR11","unstructured":"Chakraborty S, Raman V, Satti SR (2016) Biconnectivity, chain decomposition and st-numbering using \n                    \n                      \n                    \n                    $$\\text{ O }(n)$$\n                    \n                      \n                        \n                          \n                          O\n                          \n                          (\n                          n\n                          )\n                        \n                      \n                    \n                   bits. In: 27th ISAAC (LIPIcs), vol\u00a064, pp 22:1\u201322:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik"},{"key":"270_CR12","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/j.jcss.2017.06.006","volume":"90","author":"S Chakraborty","year":"2017","unstructured":"Chakraborty S, Raman V, Satti SR (2017) Biconnectivity, st-numbering and other applications of DFS using \n                    \n                      \n                    \n                    $$\\text{ O }(n)$$\n                    \n                      \n                        \n                          \n                          O\n                          \n                          (\n                          n\n                          )\n                        \n                      \n                    \n                   bits. J Comput Syst Sci 90:63\u201379","journal-title":"J Comput Syst Sci"},{"key":"270_CR13","doi-asserted-by":"crossref","unstructured":"Chakraborty S, Satti SR (2017) Space-efficient algorithms for maximum cardinality search, stack BFS, queue BFS and applications. In: 23rd COCOON, pp 87\u201398","DOI":"10.1007\/978-3-319-62389-4_8"},{"key":"270_CR14","doi-asserted-by":"crossref","unstructured":"Darwish O, Elmasry A (2014) Optimal time-space tradeoff for the 2d convex-hull problem. In: 22th ESA, pp 284\u2013295","DOI":"10.1007\/978-3-662-44777-2_24"},{"issue":"6","key":"270_CR15","doi-asserted-by":"publisher","first-page":"2257","DOI":"10.1137\/S0097539795295948","volume":"28","author":"J Edmonds","year":"1999","unstructured":"Edmonds J, Poon CK, Achlioptas D (1999) Tight lower bounds for st-connectivity on the NNJAG model. SIAM J Comput 28(6):2257\u20132284","journal-title":"SIAM J Comput"},{"key":"270_CR16","doi-asserted-by":"publisher","first-page":"835","DOI":"10.2140\/pjm.1965.15.835","volume":"15","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson DR, Gross OA (1965) Incidence matrices and interval graphs. Pac J Math 15:835\u2013855","journal-title":"Pac J Math"},{"key":"270_CR17","volume-title":"Algorithmic graph theory and perfect graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic MC (2004) Algorithmic graph theory and perfect graphs. Elsevier, Amsterdam"},{"issue":"2","key":"270_CR18","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0890-5401(92)90033-C","volume":"97","author":"R Greenlaw","year":"1992","unstructured":"Greenlaw R (1992) A model classifying algorithms as inherently sequential with applications to graph searching. Inf Comput 97(2):133\u2013149","journal-title":"Inf Comput"},{"issue":"2\u20133","key":"270_CR19","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.dam.2010.02.011","volume":"159","author":"R Krueger","year":"2011","unstructured":"Krueger R, Simonet G, Berry A (2011) A general label search to investigate classical graph search algorithms. Discrete Appl Math 159(2\u20133):128\u2013142","journal-title":"Discrete Appl Math"},{"key":"270_CR20","doi-asserted-by":"crossref","unstructured":"Munro JI (1996) Tables. In: FSTTCS, pp 37\u201342","DOI":"10.1007\/3-540-62034-6_35"},{"key":"270_CR21","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(80)90061-4","volume":"12","author":"JI Munro","year":"1980","unstructured":"Munro JI, Paterson M (1980) Selection and sorting with limited storage. Theor Comput Sci 12:315\u2013323","journal-title":"Theor Comput Sci"},{"issue":"3","key":"270_CR22","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0020-0190(96)00013-0","volume":"58","author":"BS Panda","year":"1996","unstructured":"Panda BS (1996) New linear time algorithms for generating perfect elimination orderings of chordal graphs. Inf Process Lett 58(3):111\u2013115","journal-title":"Inf Process Lett"},{"issue":"4","key":"270_CR23","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"Reingold O (2008) Undirected connectivity in log-space. J ACM 55(4):17","journal-title":"J ACM"},{"issue":"2","key":"270_CR24","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"DJ Rose","year":"1976","unstructured":"Rose DJ, Tarjan RE, Lueker GS (1976) Algorithmic aspects of vertex elimination on graphs. SIAM J Comput 5(2):266\u2013283","journal-title":"SIAM J Comput"},{"key":"270_CR25","unstructured":"Tarjan RE (1976) Maximum cardinality search and chordal graphs. Unpublished lecture notes CS 259"},{"issue":"3","key":"270_CR26","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","volume":"13","author":"RE Tarjan","year":"1984","unstructured":"Tarjan RE, Yannakakis M (1984) Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J Comput 13(3):566\u2013579","journal-title":"SIAM J Comput"},{"issue":"1","key":"270_CR27","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1137\/0211010","volume":"11","author":"M Tompa","year":"1982","unstructured":"Tompa M (1982) Two familiar transitive closure algorithms which admit no polynomial time, sublinear space implementations. SIAM J Comput 11(1):130\u2013137","journal-title":"SIAM J Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0270-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0270-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0270-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,28]],"date-time":"2019-02-28T20:44:20Z","timestamp":1551386660000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0270-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,1]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["270"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0270-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2018,3,1]]},"assertion":[{"value":"1 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}