{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,8]],"date-time":"2025-05-08T11:24:53Z","timestamp":1746703493914,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030250041"},{"type":"electronic","value":"9783030250058"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-25005-8_13","type":"book-chapter","created":{"date-parts":[[2019,7,14]],"date-time":"2019-07-14T23:02:23Z","timestamp":1563145343000},"page":"148-159","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Maximal Irredundant Set Enumeration in Bounded-Degeneracy and Bounded-Degree Hypergraphs"],"prefix":"10.1007","author":[{"given":"Alessio","family":"Conte","sequence":"first","affiliation":[]},{"given":"Mamadou Moustapha","family":"Kant\u00e9","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Marino","sequence":"additional","affiliation":[]},{"given":"Takeaki","family":"Uno","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,7,10]]},"reference":[{"issue":"1","key":"13_CR1","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BF01788542","volume":"3","author":"N Alon","year":"1987","unstructured":"Alon, N., Kahn, J., Seymour, P.D.: Large induced degenerate subgraphs. Graphs Comb. 3(1), 203\u2013211 (1987)","journal-title":"Graphs Comb."},{"issue":"4","key":"13_CR2","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1017\/S0963548309990587","volume":"19","author":"A Bar-Noy","year":"2010","unstructured":"Bar-Noy, A., Cheilaris, P., Olonetsky, S., Smorodinsky, S.: Online conflict-free colouring for hypergraphs. Comb. Probab. Comput. 19(4), 493\u2013516 (2010)","journal-title":"Comb. Probab. Comput."},{"issue":"3","key":"13_CR3","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.jda.2011.03.002","volume":"9","author":"D Binkele-Raible","year":"2011","unstructured":"Binkele-Raible, D., et al.: Breaking the 2$$^{\\text{ n }}$$-barrier for irredundance: two lines of attack. J. Discret. Algorithms 9(3), 214\u2013230 (2011)","journal-title":"J. Discret. Algorithms"},{"key":"13_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"488","DOI":"10.1007\/978-3-540-24698-5_52","volume-title":"LATIN 2004: Theoretical Informatics","author":"E Boros","year":"2004","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L.: Generating maximal independent sets for hypergraphs with bounded edge-intersections. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 488\u2013498. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24698-5_52"},{"key":"13_CR5","unstructured":"Boros, E., Makino, K.: Generating maximal irredundant and minimal redundant subfamilies of a given hypergraph. announced at WEPA 2016 (Clermont-Ferrand, November 2016) and Boolean Seminar 2017 (Liblice, March 2017) (2016). http:\/\/clp.mff.cuni.cz\/booleanseminar\/presentations\/endre.pdf"},{"key":"13_CR6","unstructured":"Conte, A., Grossi, R., Marino, A., Rizzi, R., Versari, L.: Listing subgraphs by cartesian decomposition. In: MFCS 2018, pp. 84:1\u201384:16 (2018)"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Conte, A., Kant\u00e9, M.M., Otachi, Y., Uno, T., Wasa, K.: Efficient enumeration of maximal k-degenerate induced subgraphs of a chordal graph. Theor. Comput. Sci. (2018)","DOI":"10.1007\/978-3-319-62389-4_13"},{"issue":"2","key":"13_CR8","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1137\/S009753970240639X","volume":"32","author":"T Eiter","year":"2003","unstructured":"Eiter, T., Gottlob, G., Makino, K.: New results on monotone dualization and generating hypergraph transversals. SIAM J. Comput. 32(2), 514\u2013537 (2003)","journal-title":"SIAM J. Comput."},{"issue":"11","key":"13_CR9","doi-asserted-by":"publisher","first-page":"2035","DOI":"10.1016\/j.dam.2007.04.017","volume":"156","author":"T Eiter","year":"2008","unstructured":"Eiter, T., Makino, K., Gottlob, G.: Computational aspects of monotone dualization: a brief survey. Discret. Appl. Math. 156(11), 2035\u20132049 (2008)","journal-title":"Discret. Appl. Math."},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"3.1:3.1","DOI":"10.1145\/2543629","volume":"18","author":"D Eppstein","year":"2013","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. J. Exp. Algorithmics 18, 3.1:3.1\u20133.1:3.21 (2013). https:\/\/doi.org\/10.1145\/2543629. ISSN 1084-6654, Article no. 3.1. ACM, New York","journal-title":"J. Exp. Algorithmics"},{"key":"13_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2018.02.014","volume":"754","author":"PA Golovach","year":"2019","unstructured":"Golovach, P.A., Kratsch, D., Sayadi, M.Y.: Enumeration of maximal irredundant sets for claw-free graphs. Theor. Comput. Sci. 754, 3\u201315 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"13_CR12","volume-title":"Fundamentals of Domination in Graphs","author":"TW Haynes","year":"1998","unstructured":"Haynes, T.W., Hedetniemi, S., Slater, P.: Fundamentals of Domination in Graphs. CRC Press, Boca Raton (1998)"},{"issue":"4","key":"13_CR13","doi-asserted-by":"publisher","first-page":"1916","DOI":"10.1137\/120862612","volume":"28","author":"MM Kant\u00e9","year":"2014","unstructured":"Kant\u00e9, M.M., Limouzy, V., Mary, A., Nourine, L.: On the enumeration of minimal dominating sets and related notions. SIAM J. Discret. Math. 28(4), 1916\u20131929 (2014)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"13_CR14","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s00453-007-9111-9","volume":"51","author":"L Khachiyan","year":"2008","unstructured":"Khachiyan, L., Boros, E., Borys, K., Elbassioni, K.M., Gurvich, V., Makino, K.: Generating cut conjunctions in graphs and related problems. Algorithmica 51(3), 239\u2013263 (2008)","journal-title":"Algorithmica"},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Khachiyan, L., Boros, E., Borys, K., Gurvich, V., Elbassioni, K.: Generating all vertices of a polyhedron is hard. 1\u201317 (2009)","DOI":"10.1007\/978-0-387-87363-3_17"},{"issue":"1","key":"13_CR16","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1137\/070698385","volume":"22","author":"AV Kostochka","year":"2008","unstructured":"Kostochka, A.V., Zhu, X.: Adapted list coloring of graphs and hypergraphs. SIAM J. Discret. Math. 22(1), 398\u2013408 (2008)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"13_CR17","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1137\/0209042","volume":"9","author":"EL Lawler","year":"1980","unstructured":"Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R.: Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM J. Comput. 9(3), 558\u2013565 (1980)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"13_CR18","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. 3(1), 23\u201328 (1965)","journal-title":"Isr. J. Math."},{"issue":"3","key":"13_CR19","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 the maximal independent sets. SIAM J. Comput. 6(3), 505\u2013517 (1977)","journal-title":"SIAM J. Comput."},{"key":"13_CR20","unstructured":"Wasa, K.: Enumeration of enumeration algorithms. arXiv preprint arXiv:1605.05102 (2016)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-25005-8_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T17:14:06Z","timestamp":1710350046000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-25005-8_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030250041","9783030250058"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-25005-8_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"10 July 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Pisa","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 July 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 July 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/iwoca2019.di.unipi.it\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"73","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"36","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"5-6","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}