{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,12]],"date-time":"2026-01-12T23:04:35Z","timestamp":1768259075551,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2010,11,11]],"date-time":"2010-11-11T00:00:00Z","timestamp":1289433600000},"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,4]]},"DOI":"10.1007\/s00453-010-9474-1","type":"journal-article","created":{"date-parts":[[2010,11,9]],"date-time":"2010-11-09T23:27:47Z","timestamp":1289345267000},"page":"637-658","source":"Crossref","is-referenced-by-count":23,"title":["On Independent Sets and Bicliques in Graphs"],"prefix":"10.1007","volume":"62","author":[{"given":"Serge","family":"Gaspers","sequence":"first","affiliation":[]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[]},{"given":"Mathieu","family":"Liedloff","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,11,11]]},"reference":[{"key":"9474_CR1","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1007\/3-540-45995-2_52","volume-title":"Proc. of LATIN 2002","author":"J. Alber","year":"2002","unstructured":"Alber, J., Niedermeier, R.: Improved tree decomposition based algorithms for domination-like problems. In: Proc. of LATIN 2002. LNCS, vol. 2286, pp. 613\u2013627. Springer, Berlin (2002)"},{"key":"9474_CR2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.dam.2003.09.004","volume":"145","author":"G. Alexe","year":"2004","unstructured":"Alexe, G., Alexe, S., Crama, Y., Foldes, S., Hammer, P.L., Simeone, B.: Consensus algorithms for the generation of all maximal bicliques. Discrete Appl. Math. 145, 11\u201321 (2004)","journal-title":"Discrete Appl. Math."},{"key":"9474_CR3","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/S0166-218X(98)00039-0","volume":"86","author":"J. Amilhastre","year":"1998","unstructured":"Amilhastre, J., Vilarem, M.C., Janssen, P.: Complexity of minimum biclique cover and minimum biclique decomposition for bipartite dominofree graphs. Discrete Appl. Math. 86, 125\u2013144 (1998)","journal-title":"Discrete Appl. Math."},{"key":"9474_CR4","doi-asserted-by":"crossref","first-page":"546","DOI":"10.1137\/070683933","volume":"39","author":"A. Bj\u00f6rklund","year":"2009","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Koivisto, M.: Set partitioning via inclusion\u2013exclusion. SIAM J. Comput. 39, 546\u2013563 (2009)","journal-title":"SIAM J. Comput."},{"key":"9474_CR5","first-page":"292","volume-title":"Proc. of SODA 2002","author":"V. Dahll\u00f6f","year":"2002","unstructured":"Dahll\u00f6f, V., Jonsson, P.: An algorithm for counting maximum weighted independent sets and its applications. In: Proc. of SODA 2002, pp. 292\u2013298. ACM and SIAM, Philadelphia (2002)"},{"key":"9474_CR6","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.tcs.2004.10.037","volume":"332","author":"V. Dahll\u00f6f","year":"2005","unstructured":"Dahll\u00f6f, V., Jonsson, P., Wahlstr\u00f6m, M.: Counting models for 2SAT and 3SAT formulae. Theor. Comput. Sci. 332, 265\u2013291 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9474_CR7","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1006\/jagm.2001.1199","volume":"41","author":"M. Dawande","year":"2001","unstructured":"Dawande, M., Swaminathan, J., Keskinocak, P., Tayur, S.: On bipartite and multipartite clique problems. J. Algorithms 41, 388\u2013403 (2001)","journal-title":"J. Algorithms"},{"key":"9474_CR8","unstructured":"Demaine, E.D., Gutin, G., Marx, D., Stege, U.: Open Problems\u2014Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings 07281 (2007), IBFI, Schloss Dagstuhl, Germany"},{"key":"9474_CR9","doi-asserted-by":"crossref","first-page":"240","DOI":"10.1016\/j.tcs.2005.01.014","volume":"337","author":"V.M.F. Dias","year":"2005","unstructured":"Dias, V.M.F., Herrera\u00a0de\u00a0Figueiredo, C.M., Szwarcfiter, J.L.: Generating bicliques of a graph in lexicographic order. Theor. Comput. Sci. 337, 240\u2013248 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9474_CR10","doi-asserted-by":"crossref","first-page":"1826","DOI":"10.1016\/j.dam.2007.03.017","volume":"155","author":"V.M.F. Dias","year":"2007","unstructured":"Dias, V.M.F., Herrera\u00a0de\u00a0Figueiredo, C.M., Szwarcfiter, J.L.: On the generation of bicliques of a graph. Discrete Appl. Math. 155, 1826\u20131832 (2007)","journal-title":"Discrete Appl. Math."},{"key":"9474_CR11","series-title":"LNCS","first-page":"161","volume-title":"Proc. of IWPEC 2009","author":"H. Fernau","year":"2009","unstructured":"Fernau, H., Kneis, J., Kratsch, D., Langer, A., Liedloff, M., Raible, D., Rossmanith, P.: An exact algorithm for the maximum leaf spanning tree problem. In: Proc. of IWPEC 2009. LNCS, vol. 5917, pp. 161\u2013172. Springer, Berlin (2009)"},{"key":"9474_CR12","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/s00453-007-9152-0","volume":"52","author":"F.V. Fomin","year":"2008","unstructured":"Fomin, F.V., Gaspers, S., Pyatkin, A.V., Razgon, I.: On the minimum feedback vertex set problem: Exact and enumeration algorithms. Algorithmica 52, 293\u2013307 (2008)","journal-title":"Algorithmica"},{"key":"9474_CR13","doi-asserted-by":"crossref","unstructured":"Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56 (2009)","DOI":"10.1145\/1552285.1552286"},{"key":"9474_CR14","series-title":"LNCS","first-page":"47","volume-title":"Proc. of AAIM 2007","author":"M. F\u00fcrer","year":"2007","unstructured":"F\u00fcrer, M., Kasiviswanathan, S.P.: Algorithms for counting 2-SAT solutions and colorings with applications. In: Proc. of AAIM 2007. LNCS, vol. 4508, pp. 47\u201357. Springer, Berlin (2007)"},{"key":"9474_CR15","volume-title":"Formal Concept Analysis, Mathematical Foundations","author":"B. Ganter","year":"1996","unstructured":"Ganter, B., Wille, R.: Formal Concept Analysis, Mathematical Foundations. Springer, Berlin (1996)"},{"key":"9474_CR16","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York (1979)"},{"key":"9474_CR17","unstructured":"Gaspers, S., Liedloff, M.: A branch-and-reduce algorithm for finding a minimum independent dominating set. ArXiv Report 1009.1381 [CoRR abs] (2010)"},{"key":"9474_CR18","series-title":"LNCS","first-page":"171","volume-title":"Proc. of WG 2008","author":"S. Gaspers","year":"2008","unstructured":"Gaspers, S., Kratsch, D., Liedloff, M.: On independent sets and bicliques in graphs. In: Proc. of WG 2008. LNCS, vol. 5344, pp. 171\u2013182. Springer, Berlin (2008)"},{"key":"9474_CR19","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1006\/jagm.1998.0964","volume":"29","author":"D.S. Hochbaum","year":"1998","unstructured":"Hochbaum, D.S.: Approximating clique and biclique problems. J. Algorithms 29, 174\u2013200 (1998)","journal-title":"J. Algorithms"},{"key":"9474_CR20","unstructured":"Kneis, J., Langer, A., Rossmanith, P.: A fine-grained analysis of a simple independent set algorithm. In: Proc. of FSTTCS 2009. LIPICS, vol.\u00a04, pp.\u00a0287\u2013298, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Germany"},{"key":"9474_CR21","series-title":"LNCS","first-page":"260","volume-title":"Proc. of SWAT 2004","author":"K. Makino","year":"2004","unstructured":"Makino, K., Uno, T.: New algorithms for enumerating all maximal cliques. In: Proc. of SWAT 2004. LNCS, vol. 3111, pp. 260\u2013272. Springer, Berlin (2004)"},{"key":"9474_CR22","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"J.W. Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. 3, 23\u201328 (1965)","journal-title":"Isr. J. Math."},{"key":"9474_CR23","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/S0020-0190(99)00108-8","volume":"71","author":"L. Nourine","year":"1999","unstructured":"Nourine, L., Raynaud, O.: A fast algorithm for building lattices. Inf. Process. Lett. 71, 199\u2013204 (1999)","journal-title":"Inf. Process. Lett."},{"key":"9474_CR24","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1080\/09528130210164152","volume":"14","author":"L. Nourine","year":"2002","unstructured":"Nourine, L., Raynaud, O.: A fast incremental algorithm for building lattices. J. Exp. Theor. Artif. Intell. 14, 217\u2013227 (2002)","journal-title":"J. Exp. Theor. Artif. Intell."},{"key":"9474_CR25","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.\u00a0Discrete Algorithms 6, 229\u2013242 (2008)","journal-title":"J.\u00a0Discrete Algorithms"},{"key":"9474_CR26","doi-asserted-by":"crossref","first-page":"651","DOI":"10.1016\/S0166-218X(03)00333-0","volume":"131","author":"R. Peeters","year":"2003","unstructured":"Peeters, R.: The maximum edge biclique problem is NP-complete. Discrete Appl. Math. 131, 651\u2013654 (2003)","journal-title":"Discrete Appl. Math."},{"key":"9474_CR27","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s004930070035","volume":"20","author":"E. Prisner","year":"2000","unstructured":"Prisner, E.: Bicliques in graphs\u00a0I: Bounds on their number. Combinatorica 20, 109\u2013117 (2000)","journal-title":"Combinatorica"},{"key":"9474_CR28","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0196-6774(86)90032-5","volume":"7","author":"J.M. Robson","year":"1986","unstructured":"Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7, 425\u2013440 (1986)","journal-title":"J. Algorithms"},{"key":"9474_CR29","unstructured":"van Rooij, J.M.M., Bodlaender, H.L.: Design by measure and conquer: a faster exact algorithm for dominating set. In: Proc. of STACS 2008. LIPIcs, pp. 657\u2013668. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Germany"},{"key":"9474_CR30","series-title":"LNCS","first-page":"554","volume-title":"Proc. of ESA 2009","author":"J.M.M. Rooij van","year":"2009","unstructured":"van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion\/exclusion meets measure and conquer. In: Proc. of ESA 2009. LNCS, vol. 5757, pp. 554\u2013565. Springer, Berlin (2009)"},{"key":"9474_CR31","series-title":"LNCS","first-page":"202","volume-title":"Proc. of IWPEC 2008","author":"M. Wahlstr\u00f6m","year":"2008","unstructured":"Wahlstr\u00f6m, M.: A tighter bound for counting max-weight solutions to 2SAT instances. In: Proc. of IWPEC 2008. LNCS, vol. 5018, pp. 202\u2013213. Springer, Berlin (2008)"},{"key":"9474_CR32","first-page":"253","volume-title":"Proc. of STOC 1978","author":"M. Yannakakis","year":"1978","unstructured":"Yannakakis, M.: Node and edge deletion NP-complete problems. In: Proc. of STOC 1978, pp. 253\u2013264. ACM, New York (1978)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9474-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9474-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9474-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T05:00:14Z","timestamp":1559797214000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9474-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11,11]]},"references-count":32,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["9474"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9474-1","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,11,11]]}}}