{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:28:51Z","timestamp":1762324131454,"version":"3.37.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319674278"},{"type":"electronic","value":"9783319674285"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-67428-5_13","type":"book-chapter","created":{"date-parts":[[2017,9,5]],"date-time":"2017-09-05T01:22:24Z","timestamp":1504574544000},"page":"144-160","source":"Crossref","is-referenced-by-count":3,"title":["Listing Maximal Independent Sets with Minimal Space and Bounded Delay"],"prefix":"10.1007","author":[{"given":"Alessio","family":"Conte","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Roberto","family":"Grossi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Marino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeaki","family":"Uno","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luca","family":"Versari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,9,6]]},"reference":[{"issue":"1\u20133","key":"13_CR1","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0166-218X(95)00026-N","volume":"65","author":"D Avis","year":"1996","unstructured":"Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Appl. Math. 65(1\u20133), 21\u201346 (1996)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"13_CR2","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1023\/A:1016747704458","volume":"18","author":"S Basagni","year":"2001","unstructured":"Basagni, S.: Finding a maximal weighted independent set in wireless networks. Telecommun. Syst. 18(1), 155\u2013168 (2001)","journal-title":"Telecommun. Syst."},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Brendel, W., Todorovic, S.: Segmentation as maximum-weight independent set. In: Advances in Neural Information Processing Systems, pp. 307\u2013315 (2010)","DOI":"10.1109\/CVPR.2011.5995395"},{"issue":"9","key":"13_CR4","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron, C., Kerbosch, J.: Finding all cliques of an undirected graph (algorithm 457). Commun. ACM 16(9), 575\u2013576 (1973)","journal-title":"Commun. ACM"},{"key":"13_CR5","doi-asserted-by":"crossref","unstructured":"Chang, L., Yu, J.X., Qin, L.: Fast maximal cliques enumeration in sparse graphs. Algorithmica 66(1), 173\u2013186 (2013)","DOI":"10.1007\/s00453-012-9632-8"},{"issue":"1","key":"13_CR6","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210\u2013223 (1985)","journal-title":"SIAM J. Comput."},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Cohen, S., Kimelfeld, B., Sagiv, Y.: Generating all maximal induced subgraphs for hereditary and connected-hereditary graph properties. JCSS 74(7), 1147\u20131159 (2008)","DOI":"10.1016\/j.jcss.2008.04.003"},{"key":"13_CR8","unstructured":"Comin, C., Rizzi, R.: An improved upper bound on maximal clique listing via rectangular fast matrix multiplication. CoRR, abs\/1506.01082 (2015)"},{"key":"13_CR9","unstructured":"Conte, A., Grossi, R., Marino, A., Versari, L.: Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques. In: ICALP, vol. 148, pp. 1\u201315 (2016)"},{"key":"13_CR10","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. ACM J. Exp. Algorithmics 18 (2013). Article No. 3.1"},{"key":"13_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-642-20662-7_31","volume-title":"Experimental Algorithms","author":"D Eppstein","year":"2011","unstructured":"Eppstein, D., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. In: Pardalos, P.M., Rebennack, S. (eds.) SEA 2011. LNCS, vol. 6630, pp. 364\u2013375. Springer, Heidelberg (2011). doi: 10.1007\/978-3-642-20662-7_31"},{"issue":"6","key":"13_CR12","doi-asserted-by":"crossref","first-page":"457","DOI":"10.14778\/2536336.2536346","volume":"6","author":"AW-C Fu","year":"2013","unstructured":"Fu, A.W.-C., Wu, H., Cheng, J., Wong, R.C.-W.: IS-LABEL: an independent-set based labeling scheme for point-to-point distance querying. Proc. VLDB Endow. 6(6), 457\u2013468 (2013)","journal-title":"Proc. VLDB Endow."},{"issue":"3","key":"13_CR13","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Inf. Proc. Lett. 27(3), 119\u2013123 (1988)","journal-title":"Inf. Proc. Lett."},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Leung, J.Y.-T.: Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs. J. Algorithms 5(1), 22\u201335 (1984)","DOI":"10.1016\/0196-6774(84)90037-3"},{"key":"13_CR15","unstructured":"Li, N., Latecki, L.J.: Clustering aggregation as maximum-weight independent set. In: Advances in Neural Information Processing Systems, pp. 782\u2013790 (2012)"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Loukakis, E., Tsouros, C.: A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically. Computing 27(4), 349\u2013366 (1981)","DOI":"10.1007\/BF02277184"},{"key":"13_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-540-27810-8_23","volume-title":"Algorithm Theory - SWAT 2004","author":"K Makino","year":"2004","unstructured":"Makino, K., Uno, T.: New algorithms for enumerating all maximal cliques. In: Hagerup, T., Katajainen, J. (eds.) SWAT 2004. LNCS, vol. 3111, pp. 260\u2013272. Springer, Heidelberg (2004). doi: 10.1007\/978-3-540-27810-8_23"},{"issue":"3","key":"13_CR18","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1016\/0095-8956(80)90074-X","volume":"28","author":"GJ Minty","year":"1980","unstructured":"Minty, G.J.: On maximal independent sets of vertices in claw-free graphs. J. Comb. Theor. Ser. B 28(3), 284\u2013304 (1980)","journal-title":"J. Comb. Theor. Ser. B"},{"key":"13_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/11604686_38","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"Y Okamoto","year":"2005","unstructured":"Okamoto, Y., Uno, T., Uehara, R.: Linear-time counting algorithms for independent sets in chordal graphs. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 433\u2013444. Springer, Heidelberg (2005). doi: 10.1007\/11604686_38"},{"issue":"2","key":"13_CR20","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/j.jda.2006.07.006","volume":"6","author":"Y Okamoto","year":"2008","unstructured":"Okamoto, Y., Uno, T., Uehara, R.: Counting the number of independent sets in chordal graphs. J. Discrete Algorithms 6(2), 229\u2013242 (2008)","journal-title":"J. Discrete Algorithms"},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Olteanu, A., Castillo, C., Diaz, F., Vieweg, S.: CrisisLex: a lexicon for collecting and filtering microblogged communications in crises. In: ICWSM (2014)","DOI":"10.1609\/icwsm.v8i1.14538"},{"issue":"1","key":"13_CR22","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1016\/j.tcs.2006.06.015","volume":"363","author":"E Tomita","year":"2006","unstructured":"Tomita, E., Tanaka, A., Takahashi, H.: The worst-case time complexity for generating all maximal cliques and computational experiments. TCS 363(1), 28\u201342 (2006)","journal-title":"TCS"},{"issue":"3","key":"13_CR23","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1137\/0206036","volume":"6","author":"S Tsukiyama","year":"1977","unstructured":"Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505\u2013517 (1977)","journal-title":"SIAM J. Comput."},{"key":"13_CR24","unstructured":"Uno, T.: Two general methods to reduce delay and change of enumeration algorithms. National Institute of Informatics (in Japan) (2003). TR E, 4"},{"issue":"1\u20132","key":"13_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1080\/00207169308804157","volume":"47","author":"C-W Yu","year":"1993","unstructured":"Yu, C.-W., Chen, G.H.: Generate all maximal independent sets in permutation graphs. Int. J. Comput. Math. 47(1\u20132), 1\u20138 (1993)","journal-title":"Int. J. Comput. Math."}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-67428-5_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T12:08:36Z","timestamp":1692965316000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-67428-5_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319674278","9783319674285"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-67428-5_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}