{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T06:12:40Z","timestamp":1762323160523},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T00:00:00Z","timestamp":1193443200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/2.0"},{"start":{"date-parts":[[2007,10,27]],"date-time":"2007-10-27T00:00:00Z","timestamp":1193443200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,7]]},"DOI":"10.1007\/s00453-007-9111-9","type":"journal-article","created":{"date-parts":[[2007,10,26]],"date-time":"2007-10-26T16:11:10Z","timestamp":1193415070000},"page":"239-263","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Generating Cut Conjunctions in Graphs and Related\u00a0Problems"],"prefix":"10.1007","volume":"51","author":[{"given":"Leonid","family":"Khachiyan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Endre","family":"Boros","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konrad","family":"Borys","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Khaled","family":"Elbassioni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vladimir","family":"Gurvich","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuhisa","family":"Makino","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,10,27]]},"reference":[{"key":"9111_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1007\/978-3-540-28629-5_21","volume-title":"Mathematical Foundations of Computer Science MFCS","author":"E. Boros","year":"2004","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L., Makino, K.: Generating paths and cuts in multi-pole (di)graphs. In: Fiala, J., Koubek, V., Kratochvil, J. (eds.) Mathematical Foundations of Computer Science MFCS, Prague, Czech Republic, August 22\u201327, 2004. Lecture Notes in Computer Science, vol.\u00a03153, pp. 298\u2013309. Springer, Berlin (2004)"},{"issue":"4","key":"9111_CR2","doi-asserted-by":"publisher","first-page":"966","DOI":"10.1137\/S0895480103428338","volume":"19","author":"E. Boros","year":"2005","unstructured":"Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L., Makino, K.: On the complexity of some enumeration problems for matroids. SIAM J. Discrete Math. 19(4), 966\u2013984 (2005)","journal-title":"SIAM J. Discrete Math."},{"issue":"3","key":"9111_CR3","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1002\/jgt.20180","volume":"53","author":"E. Boros","year":"2006","unstructured":"Boros, E., Elbassioni, K., Gurvich, V.: Transversal hypergraphs to perfect matchings in bipartite graphs: characterization and generation algorithms. J. Graph Theory 53(3), 209\u2013232 (2006)","journal-title":"J. Graph Theory"},{"key":"9111_CR4","doi-asserted-by":"crossref","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiway cuts. In: Proceedings of the 24th ACM Symposium on Theory of Computing, pp. 241\u2013251 (1992)","DOI":"10.1145\/129712.129736"},{"key":"9111_CR5","doi-asserted-by":"publisher","first-page":"1278","DOI":"10.1137\/S0097539793250299","volume":"24","author":"T. Eiter","year":"1995","unstructured":"Eiter, T., Gottlob, G.: Identifying the minimal transversals of a hypergraph and related problems. SIAM J. Comput. 24, 1278\u20131304 (1995)","journal-title":"SIAM J. Comput."},{"key":"9111_CR6","doi-asserted-by":"publisher","first-page":"618","DOI":"10.1006\/jagm.1996.0062","volume":"21","author":"M. Fredman","year":"1996","unstructured":"Fredman, M., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms. J. Algorithms 21, 618\u2013628 (1996)","journal-title":"J. Algorithms"},{"key":"9111_CR7","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1287\/opre.11.3.344","volume":"11","author":"T.C. Hu","year":"1963","unstructured":"Hu, T.C.: Multicomodity network flows. Oper. Res. 11, 344\u2013360 (1963)","journal-title":"Oper. Res."},{"key":"9111_CR8","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., Papadimitriou, C.H.: On generating all maximal independent sets. Inf. Process. Lett. 27, 119\u2013123 (1988)","journal-title":"Inf. Process. Lett."},{"key":"9111_CR9","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1137\/0209042","volume":"9","author":"E. Lawler","year":"1980","unstructured":"Lawler, E., Lenstra, J.K., Rinnooy Kan, A.H.G.: Generating all maximal independent sets NP-hardness and polynomial-time algorithms. SIAM J. Comput. 9, 558\u2013565 (1980)","journal-title":"SIAM J. Comput."},{"key":"9111_CR10","volume-title":"Matroid Theory","author":"J.G. Oxley","year":"1992","unstructured":"Oxley, J.G.: Matroid Theory. Oxford University Press, Oxford (1992)"},{"key":"9111_CR11","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1002\/net.1975.5.3.237","volume":"5","author":"R.C. Read","year":"1975","unstructured":"Read, R.C., Tarjan, R.E.: Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5, 237\u2013252 (1975)","journal-title":"Networks"},{"key":"9111_CR12","volume-title":"Combinatorial Optimization Polyhedra and Efficiency","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization Polyhedra and Efficiency, vol.\u00a0B. Springer, Berlin (2003). p.\u00a0654"},{"issue":"1\u20133","key":"9111_CR13","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1016\/S0166-218X(00)00339-5","volume":"117","author":"B. Schwikowski","year":"2002","unstructured":"Schwikowski, B., Speckenmeyer, E.: On enumerating all minimal solutions of feedback problems. Discrete Appl. Math. 117(1\u20133), 253\u2013265 (2002)","journal-title":"Discrete Appl. Math."},{"key":"9111_CR14","first-page":"331","volume":"38","author":"A. Shioura","year":"1995","unstructured":"Shioura, A., Tamura, A.: Efficiently scanning all spanning trees of an undirected graph. J. Oper. Res. 38, 331\u2013344 (1995)","journal-title":"J. Oper. Res."},{"key":"9111_CR15","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/0020-0190(74)90003-9","volume":"2","author":"R. Tarjan","year":"1974","unstructured":"Tarjan, R.: A note on finding the bridges of a graph. Inf. Process. Lett. 2, 160\u2013161 (1974)","journal-title":"Inf. Process. Lett."},{"key":"9111_CR16","doi-asserted-by":"crossref","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. Assoc. Comput. Mach. 27, 619\u2013632 (1980)","journal-title":"J. Assoc. Comput. Mach."},{"key":"9111_CR17","volume-title":"Approximation Algorithms","author":"V. Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Berlin (2001)"},{"key":"9111_CR18","volume-title":"Matroid Theory","author":"D.J.A. Welsh","year":"1976","unstructured":"Welsh, D.J.A.: Matroid Theory. Academic, London (1976)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9111-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-007-9111-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9111-9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9111-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,31]],"date-time":"2021-08-31T19:30:42Z","timestamp":1630438242000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-007-9111-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,27]]},"references-count":18,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,7]]}},"alternative-id":["9111"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9111-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10,27]]},"assertion":[{"value":"9 February 2006","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 November 2006","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2007","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}