{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T06:35:38Z","timestamp":1774334138607,"version":"3.50.1"},"publisher-location":"Singapore","reference-count":34,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819571260","type":"print"},{"value":"9789819571277","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-981-95-7127-7_37","type":"book-chapter","created":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T10:07:13Z","timestamp":1770977233000},"page":"560-575","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the\u00a0Complexity of\u00a0Hyperpath and\u00a0Minimal Separator Enumeration in\u00a0Directed Hypergraphs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7638-3322","authenticated-orcid":false,"given":"Kazuhiro","family":"Kurita","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0880-2513","authenticated-orcid":false,"given":"Kevin","family":"Mann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,14]]},"reference":[{"key":"37_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/3-540-56402-0_55","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"P Alimonti","year":"1993","unstructured":"Alimonti, P., Feuerstein, E.: Petri nets, hypergraphs and conflicts (preliminary version). In: Mayr, E.W. (ed.) WG 1992. LNCS, vol. 657, pp. 293\u2013309. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-56402-0_55"},{"issue":"4","key":"37_CR2","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1016\/j.tcs.2010.09.030","volume":"412","author":"P Alimonti","year":"2011","unstructured":"Alimonti, P., Feuerstein, E., Laura, L., Nanni, U.: Linear time analysis of properties of conflict-free and general petri nets. Theor. Comput. Sci. 412(4), 320\u2013338 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"37_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0023812","volume-title":"LATIN \u201992","author":"P Alimonti","year":"1992","unstructured":"Alimonti, P., Feuerstein, E., Nanni, U.: Linear time algorithms for liveness and boundedness in conflict-free Petri nets. In: Simon, I. (ed.) LATIN 1992. LNCS, vol. 583, pp. 1\u201314. Springer, Heidelberg (1992). https:\/\/doi.org\/10.1007\/BFb0023812"},{"issue":"2","key":"37_CR4","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1007\/s00453-012-9729-0","volume":"69","author":"X Allamigeon","year":"2014","unstructured":"Allamigeon, X.: On the complexity of strongly connected components in directed hypergraphs. Algorithmica 69(2), 335\u2013369 (2014)","journal-title":"Algorithmica"},{"issue":"1","key":"37_CR5","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/j.jda.2003.12.005","volume":"3","author":"G Ausiello","year":"2005","unstructured":"Ausiello, G., Franciosa, P.G., Frigioni, D.: Partially dynamic maintenance of minimum weight hyperpaths. J. Discrete Algorithms 3(1), 27\u201346 (2005)","journal-title":"J. Discrete Algorithms"},{"key":"37_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-32147-4_1","volume-title":"Combinatorial Optimization","author":"G Ausiello","year":"2012","unstructured":"Ausiello, G., Italiano, G.F., Laura, L., Nanni, U., Sarracco, F.: Structure theorems for optimum hyperpaths in directed hypergraphs. In: Mahjoub, A.R., Markakis, V., Milis, I., Paschos, V.T. (eds.) ISCO 2012. LNCS, vol. 7422, pp. 1\u201314. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32147-4_1"},{"key":"37_CR7","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/j.tcs.2016.03.016","volume":"658","author":"G Ausiello","year":"2017","unstructured":"Ausiello, G., Laura, L.: Directed hypergraphs: introduction and fundamental algorithms\u2013a survey. Theor. Comput. Sci. 658, 293\u2013306 (2017)","journal-title":"Theor. Comput. Sci."},{"key":"37_CR8","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.tcs.2020.12.021","volume":"856","author":"K B\u00e9rczi","year":"2021","unstructured":"B\u00e9rczi, K.: Generating clause sequences of a CNF formula. Theor. Comput. Sci. 856, 68\u201374 (2021)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"37_CR9","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1002\/mcda.1603","volume":"24","author":"F B\u00f6kler","year":"2017","unstructured":"B\u00f6kler, F., Ehrgott, M., Morris, C., Mutzel, P.: Output-sensitive complexity of multiobjective combinatorial optimization. J. Multi-Criteria Decis. Anal. 24(1\u20132), 25\u201336 (2017)","journal-title":"J. Multi-Criteria Decis. Anal."},{"issue":"3","key":"37_CR10","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1142\/S0129054100000211","volume":"11","author":"A Berry","year":"2000","unstructured":"Berry, A., Bordat, J.P., Cogis, O.: Generating all the minimal separators of a graph. Int. J. Found. Comput. Sci. 11(3), 397\u2013403 (2000)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"37_CR11","doi-asserted-by":"crossref","unstructured":"Birmel\u00e9, E., et al.: Optimal listing of cycles and st-paths in undirected graphs. In: Proceedings of the SODA 2013, pp. 118\u2013128. SIAM (2013)","DOI":"10.1137\/1.9781611973105.134"},{"key":"37_CR12","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/j.dam.2024.07.006","volume":"358","author":"E Boros","year":"2024","unstructured":"Boros, E., Makino, K.: Generating minimal redundant and maximal irredundant subhypergraphs. Discret. Appl. Math. 358, 217\u2013229 (2024)","journal-title":"Discret. Appl. Math."},{"key":"37_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2023.106469","volume":"185","author":"C Brosse","year":"2024","unstructured":"Brosse, C.: On the hardness of inclusion-wise minimal separators enumeration. Inf. Process. Lett. 185, 106469 (2024)","journal-title":"Inf. Process. Lett."},{"issue":"9","key":"37_CR14","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1016\/j.aml.2007.07.031","volume":"21","author":"C \u00d6zturan","year":"2008","unstructured":"\u00d6zturan, C.: On finding hypercycles in chemical reaction networks. Appl. Math. Lett. 21(9), 881\u2013884 (2008)","journal-title":"Appl. Math. Lett."},{"key":"37_CR15","unstructured":"Creignou, N., Defrain, O., Olive, F., Vilmin, S.: On the enumeration of signatures of XOR-CNF\u2019s. In: Proceedings of the WADS 2025, vol. 349 of LIPIcs, pp. 19:1\u201319:14, Dagstuhl, Germany, 2025. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik"},{"key":"37_CR16","doi-asserted-by":"crossref","unstructured":"Eiter, T., Makino, K., Gottlob, G.: Computational aspects of monotone dualization: a brief survey. Discrete Appl. Math. 156(11), 2035\u20132049 (2008). In Memory of Leonid Khachiyan (1952 - 2005 )","DOI":"10.1016\/j.dam.2007.04.017"},{"issue":"3","key":"37_CR17","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1006\/jagm.1996.0062","volume":"21","author":"ML Fredman","year":"1996","unstructured":"Fredman, M.L., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms. J. Algorithms 21(3), 618\u2013628 (1996)","journal-title":"J. Algorithms"},{"issue":"2","key":"37_CR18","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/BF01581727","volume":"80","author":"G Gallo","year":"1998","unstructured":"Gallo, G., Gentile, C., Pretolani, D., Rago, G.: Max Horn SAT and the minimum cut problem in directed hypergraphs. Math. Program. 80(2), 213\u2013237 (1998)","journal-title":"Math. Program."},{"issue":"2","key":"37_CR19","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0166-218X(93)90045-P","volume":"42","author":"G Gallo","year":"1993","unstructured":"Gallo, G., Longo, G., Pallottino, S., Nguyen, S.: Directed hypergraphs and applications. Discrete Appl. Math. 42(2), 177\u2013201 (1993)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"37_CR20","first-page":"97","volume":"21","author":"G Gallo","year":"1998","unstructured":"Gallo, G., Scutell\u00e0, M.G.: Directed hypergraphs as a modelling paradigm. Riv. Mat. Sci. Econom. Social. 21(1), 97\u2013123 (1998)","journal-title":"Riv. Mat. Sci. Econom. Social."},{"issue":"3","key":"37_CR21","doi-asserted-by":"publisher","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. Process. Lett. 27(3), 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"37_CR22","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1007\/s00453-007-9074-x","volume":"50","author":"L Khachiyan","year":"2008","unstructured":"Khachiyan, L., Boros, E., Elbassioni, K.M., Gurvich, V.: On enumerating minimal dicuts and strongly connected subgraphs. Algorithmica 50(1), 159\u2013172 (2008)","journal-title":"Algorithmica"},{"issue":"4","key":"37_CR23","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.is.2008.01.002","volume":"33","author":"B Kimelfeld","year":"2008","unstructured":"Kimelfeld, B., Sagiv, Y.: Efficiently enumerating results of keyword search over data graphs. Inf. Syst. 33(4), 335\u2013359 (2008)","journal-title":"Inf. Syst."},{"key":"37_CR24","doi-asserted-by":"crossref","unstructured":"Kobayashi, Y., Kurita, K., Wasa, K.: Linear-delay enumeration for minimal Steiner problems. In: Proceedings of the PODS 2022, PODS \u201922, pp. 301\u2013313, New York, NY, USA (2022). Association for Computing Machinery","DOI":"10.1145\/3517804.3524148"},{"issue":"11","key":"37_CR25","doi-asserted-by":"publisher","first-page":"1198","DOI":"10.1089\/cmb.2023.0242","volume":"30","author":"S Krieger","year":"2023","unstructured":"Krieger, S., Kececioglu, J.: Shortest hyperpaths in directed hypergraphs for reaction pathway inference. J. Comput. Biol. 30(11), 1198\u20131225 (2023). PMID: 37906100","journal-title":"J. Comput. Biol."},{"key":"37_CR26","unstructured":"Kurita, K., Kobayashi, Y.: Efficient enumerations for minimal multicuts and multiway cuts. In: Proceedings of the MFCS 2020, vol. 170 of LIPIcs, pp. 60:1\u201360:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"key":"37_CR27","unstructured":"Nielsen, L.R., Pretolani, D., Andersen, K.: A remark on the definition of a B-hyperpath. Technical report, Department of Operations Research, University of Aarhus, Technical report (2001)"},{"issue":"4","key":"37_CR28","first-page":"351","volume":"15","author":"JS Provan","year":"1996","unstructured":"Provan, J.S., Shier, D.R.: A paradigm for listing $$(s, t)$$-cuts in graphs. Algorithmica 15(4), 351\u2013372 (1996)","journal-title":"Algorithmica"},{"issue":"3","key":"37_CR29","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1002\/net.1975.5.3.237","volume":"5","author":"RC Read","year":"1975","unstructured":"Read, R.C., Tarjan, R.E.: Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5(3), 237\u2013252 (1975)","journal-title":"Networks"},{"issue":"15","key":"37_CR30","doi-asserted-by":"publisher","first-page":"1660","DOI":"10.1016\/j.dam.2010.05.013","volume":"158","author":"K Takata","year":"2010","unstructured":"Takata, K.: Space-optimal, backtracking algorithms to list the minimal vertex separators of a graph. Discrete Appl. Math. 158(15), 1660\u20131667 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"27","key":"37_CR31","doi-asserted-by":"publisher","first-page":"2592","DOI":"10.1016\/j.tcs.2009.02.038","volume":"410","author":"M Thakur","year":"2009","unstructured":"Thakur, M., Tripathi, R.: Linear connectivity problems in directed hypergraphs. Theor. Comput. Sci. 410(27), 2592\u20132618 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"37_CR32","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1145\/322217.322220","volume":"27","author":"S Tsukiyama","year":"1980","unstructured":"Tsukiyama, S., Shirakawa, I., Ozaki, H., Ariyoshi, H.: An algorithm to enumerate all cutsets of a graph in linear time per cutset. J. ACM 27(4), 619\u2013632 (1980)","journal-title":"J. ACM"},{"key":"37_CR33","doi-asserted-by":"publisher","unstructured":"Uno, T., Satoh, H.: An efficient algorithm for enumerating Chordless cycles and Chordless paths. In: D\u017eeroski, S., et al. (eds.) DS 2014. LNCS (LNAI), vol. 8777, pp. 313\u2013324. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11812-3_27","DOI":"10.1007\/978-3-319-11812-3_27"},{"issue":"2","key":"37_CR34","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1016\/j.ejor.2007.04.023","volume":"188","author":"AP Volpentesta","year":"2008","unstructured":"Volpentesta, A.P.: Hypernetworks in a directed hypergraph. Eur. J. Oper. Res. 188(2), 390\u2013405 (2008)","journal-title":"Eur. J. Oper. Res."}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-7127-7_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T04:13:36Z","timestamp":1774325616000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-7127-7_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9789819571260","9789819571277"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-7127-7_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"14 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Perugia","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":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 March 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 March 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/mozart.diei.unipg.it\/walcom2026","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}