{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T16:44:03Z","timestamp":1725900243628},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642385261"},{"type":"electronic","value":"9783642385278"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38527-8_11","type":"book-chapter","created":{"date-parts":[[2013,5,8]],"date-time":"2013-05-08T13:23:02Z","timestamp":1368019382000},"page":"103-114","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Counting of Maximal Independent Sets in Sparse Graphs"],"prefix":"10.1007","author":[{"given":"Fredrik","family":"Manne","sequence":"first","affiliation":[]},{"given":"Sadia","family":"Sharmin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"11_CR1","doi-asserted-by":"publisher","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. Com. ACM\u00a016, 575\u2013577 (1973)","journal-title":"Com. ACM"},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Cheng, J., Ke, Y., Fuu, W., Xu Yu, J.: Finding maximal cliques in massive networks. ACM Trans. Database Syst. 36(4), 21:1 \u2013 21:34 (2011)","DOI":"10.1145\/2043652.2043654"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"1240","DOI":"10.1145\/2339530.2339724","volume-title":"Proc. of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2012","author":"J. Cheng","year":"2012","unstructured":"Cheng, J., Zhu, L., Ke, Y., Chu, S.: Fast algorithms for maximal clique enumeration with limited memory. In: Proc. of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2012, pp. 1240\u20131248. ACM, New York (2012)"},{"issue":"3","key":"11_CR4","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1137\/S089547980240563X","volume":"26","author":"S.C. Eisenstat","year":"2005","unstructured":"Eisenstat, S.C., Liu, J.W.H.: The theory of elimination trees for sparse unsymmetric matrices. SIAM J. Mat. Anal. App.\u00a026(3), 686\u2013705 (2005)","journal-title":"SIAM J. Mat. Anal. App."},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Eppstein, D.: All maximal independent sets and dynamic dominance for sparse graphs. ACM Trans. on Alg. 5 (2009)","DOI":"10.1145\/1597036.1597042"},{"key":"11_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/978-3-642-17517-6_36","volume-title":"Algorithms and Computation","author":"D. Eppstein","year":"2010","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in sparse graphs in near-optimal time. In: Cheong, O., Chwa, K.-Y., Park, K. (eds.) ISAAC 2010, Part I. LNCS, vol.\u00a06506, pp. 403\u2013414. Springer, Heidelberg (2010)"},{"key":"11_CR7","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.\u00a06630, pp. 364\u2013375. Springer, Heidelberg (2011)"},{"key":"11_CR8","doi-asserted-by":"crossref","unstructured":"Gaspers, S., Kratsch, D., Liedloff, M.: On independent sets and bicliques in graphs. Journal of Graph Theoritic Concepts in Computer Science, 171\u2013182 (2008)","DOI":"10.1007\/978-3-540-92248-3_16"},{"issue":"2","key":"11_CR9","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1137\/0710032","volume":"10","author":"A. George","year":"1973","unstructured":"George, A.: Nested dissection of a regular finite element mesh. SIAM J. on Num. Anal.\u00a010(2), 345\u2013363 (1973)","journal-title":"SIAM J. on Num. Anal."},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"D.S. Johnson","year":"1988","unstructured":"Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Information Processing Letters\u00a027, 119\u2013123 (1988)","journal-title":"Information Processing Letters"},{"key":"11_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-3-642-27660-6_27","volume-title":"SOFSEM 2012: Theory and Practice of Computer Science","author":"K. Junosza-Szaniawski","year":"2012","unstructured":"Junosza-Szaniawski, K., Tuczy\u0144ski, M.: Counting maximal independent sets in subcubic graphs. In: Bielikov\u00e1, M., Friedrich, G., Gottlob, G., Katzenbeisser, S., Tur\u00e1n, G. (eds.) SOFSEM 2012. LNCS, vol.\u00a07147, pp. 325\u2013336. Springer, Heidelberg (2012)"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1137\/0209042","volume":"9","author":"E.L. Lawler","year":"1980","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Generating all maximal independent sets: NP-hardness and polynomial time algorithms. SIAM J. Comp.\u00a09, 558\u2013565 (1980)","journal-title":"SIAM J. Comp."},{"issue":"3","key":"11_CR13","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comp.\u00a09(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comp."},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02277184","volume":"4","author":"E. Loukakis","year":"1981","unstructured":"Loukakis, E., Tsouros, C.: A depth first search algorithm to generate the family of maximal independent sets of a graph lexicographically. Computing\u00a04, 349\u2013366 (1981)","journal-title":"Computing"},{"key":"11_CR15","unstructured":"Metis - serial graph partitioning and fill-reducing matrix ordering, http:\/\/glaros.dtc.umn.edu\/gkhome\/views\/metis\/"},{"key":"11_CR16","doi-asserted-by":"crossref","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Israel J. of Math., 23\u201328 (1965)","DOI":"10.1007\/BF02760024"},{"key":"11_CR17","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.\u00a03787, pp. 433\u2013444. Springer, Heidelberg (2005)"},{"key":"11_CR18","doi-asserted-by":"publisher","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. Theor. Comput. Sci.\u00a0363, 28\u201342 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"11_CR19","unstructured":"Treewidthlib (2004-.), http:\/\/www.cs.uu.nl\/people\/hansb\/treewidthlib"},{"key":"11_CR20","doi-asserted-by":"publisher","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 maximal independent sets. SIAM J. Comp.\u00a06, 505\u2013517 (1977)","journal-title":"SIAM J. Comp."},{"issue":"1","key":"11_CR21","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1137\/0607015","volume":"7","author":"H.S. Wilf","year":"1986","unstructured":"Wilf, H.S.: The number of maximal independent sets in a tree. SIAM J. Alg. Disc. Meth.\u00a07(1), 125\u2013130 (1986)","journal-title":"SIAM J. Alg. Disc. Meth."}],"container-title":["Lecture Notes in Computer Science","Experimental Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38527-8_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,13]],"date-time":"2019-07-13T14:57:56Z","timestamp":1563029876000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38527-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642385261","9783642385278"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38527-8_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}