{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:57:38Z","timestamp":1781305058655,"version":"3.54.1"},"publisher-location":"Cham","reference-count":45,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032286901","type":"print"},{"value":"9783032286918","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-3-032-28691-8_14","type":"book-chapter","created":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:35:35Z","timestamp":1781303735000},"page":"204-219","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Lattice Structure and\u00a0Efficient Basis Construction for\u00a0Strongly Connected Orientations"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3553-9431","authenticated-orcid":false,"given":"Siyue","family":"Liu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-1389-8346","authenticated-orcid":false,"given":"Olha","family":"Silina","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,13]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","unstructured":"Abdi, A., Cornu\u00e9jols, G., Guenin, B., Tun\u00e7el, L.: Dyadic linear programming and extensions. Math. Program. 1\u201344 (2024)","DOI":"10.1007\/s10107-024-02146-4"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Abdi, A., Cornu\u00e9jols, G., Liu, S., Silina, O.: Strongly connected orientations and integer lattices. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 1\u201314. Springer (2025)","DOI":"10.1007\/978-3-031-93112-3_1"},{"issue":"4","key":"14_CR3","doi-asserted-by":"publisher","first-page":"2417","DOI":"10.1137\/22M1506511","volume":"37","author":"A Abdi","year":"2023","unstructured":"Abdi, A., Cornu\u00e9jols, G., Zlatin, M.: On packing dijoins in digraphs and weighted digraphs. SIAM J. Discret. Math. 37(4), 2417\u20132461 (2023)","journal-title":"SIAM J. Discret. Math."},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Abdi, A., Cornu\u00e9jols, G., Liu, S., Silina, O.: Strongly connected orientations and integer lattices (2024). https:\/\/arxiv.org\/abs\/2410.13665","DOI":"10.1007\/978-3-031-93112-3_1"},{"key":"14_CR5","unstructured":"Abdi, A., Silina, O.: Integral bases, perfect matchings, and the petersen graph. arXiv preprint arXiv:2508.15602 (2025)"},{"key":"14_CR6","doi-asserted-by":"publisher","unstructured":"Artmann, S., Weismantel, R., Zenklusen, R.: A strongly polynomial algorithm for bimodular integer linear programming. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pp. 1206\u20131219. Association for Computing Machinery, New York, NY, USA (2017). https:\/\/doi.org\/10.1145\/3055399.3055473","DOI":"10.1145\/3055399.3055473"},{"key":"14_CR7","doi-asserted-by":"crossref","unstructured":"Balas, E.: Integer and fractional matchings. In: North-Holland Mathematics Studies, vol.\u00a059, pp. 1\u201313. Elsevier (1981)","DOI":"10.1016\/S0304-0208(08)73453-4"},{"key":"14_CR8","unstructured":"Bang-Jensen, J., Gutin, G.: Theory, algorithms and applications. Monographs in Mathematics (2000)"},{"key":"14_CR9","unstructured":"Carvalho, M.H.: Decomposicao Otima em Orelhas Para Grafos Matching Covered. Ph.D. thesis, University of Campinas, Brasil, 1986. In Portuguese (1997)"},{"issue":"1","key":"14_CR10","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1006\/jctb.2001.2090","volume":"85","author":"MH de Carvalho","year":"2002","unstructured":"de Carvalho, M.H., Lucchesi, C.L., Murty, U.S.R.: Optimal ear decompositions of matching covered graphs and bases for the matching lattice. J. Comb. Theory Ser. B 85(1), 59\u201393 (2002). https:\/\/doi.org\/10.1006\/jctb.2001.2090","journal-title":"J. Comb. Theory Ser. B"},{"issue":"2","key":"14_CR11","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s004930050051","volume":"19","author":"MH Carvalho","year":"1999","unstructured":"Carvalho, M.H., Lucchesi, C.L., Murty, U.S.: Ear decompositions of matching covered graphs. Combinatorica 19(2), 151\u2013174 (1999)","journal-title":"Combinatorica"},{"issue":"2","key":"14_CR12","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/j.jctb.2004.08.003","volume":"92","author":"MH de Carvalho","year":"2004","unstructured":"de Carvalho, M.H., Lucchesi, C.L., Murty, U.S.: The perfect matching polytope and solid bricks. J. Comb. Theory Ser. B 92(2), 319\u2013324 (2004)","journal-title":"J. Comb. Theory Ser. B"},{"key":"14_CR13","doi-asserted-by":"publisher","unstructured":"de\u00a0Carvalho, M.H., Lucchesi, C.L., Murty, U.S.R.: On a conjecture of lov\u00e1sz concerning bricks: I. the characteristic of a matching covered graph. J. Comb. Theory Ser. B 85(1), 94\u2013136 (2002). https:\/\/doi.org\/10.1006\/jctb.2001.2091","DOI":"10.1006\/jctb.2001.2091"},{"key":"14_CR14","doi-asserted-by":"publisher","unstructured":"de\u00a0Carvalho, M.H., Lucchesi, C.L., Murty, U.S.R.: On a conjecture of lov\u00e1sz concerning bricks: Ii. bricks of finite characteristic. J. Comb. Theory Ser. B 85(1), 137\u2013180 (2002). https:\/\/doi.org\/10.1006\/jctb.2001.2092","DOI":"10.1006\/jctb.2001.2092"},{"issue":"3","key":"14_CR15","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/s00493-025-00159-x","volume":"45","author":"G Cornu\u00e9jols","year":"2025","unstructured":"Cornu\u00e9jols, G., Liu, S., Ravi, R.: Approximately packing dijoins via nowhere-zero flows. Combinatorica 45(3), 32 (2025)","journal-title":"Combinatorica"},{"issue":"3","key":"14_CR16","doi-asserted-by":"publisher","first-page":"1769","DOI":"10.1137\/18M1202347","volume":"34","author":"MH De Carvalho","year":"2020","unstructured":"De Carvalho, M.H., Kothari, N., Wang, X., Lin, Y.: Birkhoff-von neumann graphs that are pm-compact. SIAM J. Discret. Math. 34(3), 1769\u20131790 (2020)","journal-title":"SIAM J. Discret. Math."},{"issue":"19\u201320","key":"14_CR17","doi-asserted-by":"publisher","first-page":"2383","DOI":"10.1016\/j.disc.2005.12.032","volume":"306","author":"MH De Carvalho","year":"2006","unstructured":"De Carvalho, M.H., Lucchesi, C.L., Murty, U.S.: How to build a brick. Discret. Math. 306(19\u201320), 2383\u20132410 (2006)","journal-title":"Discret. Math."},{"issue":"3","key":"14_CR18","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/BF02579233","volume":"2","author":"J Edmonds","year":"1982","unstructured":"Edmonds, J., Pulleyblank, W.R., Lov\u00e1sz, L.: Brick decompositions and the matching rank of graphs. Combinatorica 2(3), 247\u2013274 (1982). https:\/\/doi.org\/10.1007\/BF02579233","journal-title":"Combinatorica"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Giles, R.: A min-max relation for submodular functions on graphs. In: Studies in Integer Programming (Proc. Workshop, Bonn, 1975), pp. 185\u2013204. Annals of Discrete Mathematics, vol. 1 (1977)","DOI":"10.1016\/S0167-5060(08)70734-9"},{"key":"14_CR20","doi-asserted-by":"crossref","unstructured":"Eisenbrand, F., Rohwedder, L., Wegrzycki, K.: Sensitivity, proximity and FPT algorithms for exact matroid problems. In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1610\u20131620. IEEE (2024)","DOI":"10.1109\/FOCS61266.2024.00100"},{"key":"14_CR21","unstructured":"Frank, A.: Connections in Combinatorial Optimization. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press (2011)"},{"key":"14_CR22","first-page":"353","volume":"18","author":"A Frank","year":"1978","unstructured":"Frank, A., Gy\u00e1rf\u00e1s, A.: How to orient the edges of a graph. Combinatorics 18, 353\u2013362 (1978)","journal-title":"Combinatorics"},{"key":"14_CR23","doi-asserted-by":"crossref","unstructured":"Frank, A., Tardos, \u00c9.: Matroids from crossing families. In: Finite and Infinite Sets, pp. 295\u2013304. Elsevier (1984)","DOI":"10.1016\/B978-0-444-86893-0.50022-X"},{"issue":"1","key":"14_CR24","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1007\/BF02591852","volume":"38","author":"AMH Gerards","year":"1987","unstructured":"Gerards, A.M.H., Seb\u0151, A.: Total dual integrality implies local strong unimodularity. Math. Program. 38(1), 69\u201373 (1987). https:\/\/doi.org\/10.1007\/BF02591852","journal-title":"Math. Program."},{"issue":"1","key":"14_CR25","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1137\/24M1647692","volume":"39","author":"B Guenin","year":"2025","unstructured":"Guenin, B., Hwang, S.: Dyadic packing of dijoins. SIAM J. Discret. Math. 39(1), 593\u2013606 (2025)","journal-title":"SIAM J. Discret. Math."},{"key":"14_CR26","unstructured":"H\u00f6rsch, F., Imolay, A., Mizutani, R., Oki, T., Schwarcz, T.: Problems on group-labeled matroid bases. arXiv preprint arXiv:2402.16259 (2024)"},{"key":"14_CR27","unstructured":"Liu, S., Silina, O.: Lattice structure and efficient basis construction for strongly connected orientations. arXiv preprint arXiv:2603.17424 (2026). https:\/\/arxiv.org\/abs\/2603.17424"},{"key":"14_CR28","doi-asserted-by":"crossref","unstructured":"Liu, S., Xu, C.: On the congruency-constrained matroid base. In: International Conference on Integer Programming and Combinatorial Optimization, pp. 280\u2013293. Springer (2024)","DOI":"10.1007\/978-3-031-59835-7_21"},{"issue":"2","key":"14_CR29","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0095-8956(87)90021-9","volume":"43","author":"L Lov\u00e1sz","year":"1987","unstructured":"Lov\u00e1sz, L.: Matching structure and the matching lattice. J. Comb. Theory Ser. B 43(2), 187\u2013222 (1987). https:\/\/doi.org\/10.1016\/0095-8956(87)90021-9","journal-title":"J. Comb. Theory Ser. B"},{"key":"14_CR30","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Plummer, M.D.: Matching Theory, vol.\u00a0367. AMS Chelsea Publishing (2009)","DOI":"10.1090\/chel\/367"},{"key":"14_CR31","doi-asserted-by":"publisher","unstructured":"Lucchesi, C.L., Younger, D.H.: A minimax theorem for directed graphs. J. London Math. Soc. (2) 17(3), 369\u2013374 (1978). https:\/\/doi.org\/10.1112\/jlms\/s2-17.3.369","DOI":"10.1112\/jlms\/s2-17.3.369"},{"key":"14_CR32","doi-asserted-by":"publisher","unstructured":"Lucchesi, C.L., Murty, U.S.R.: Perfect Matchings: A Theory of Matching Covered Graphs, Algorithms and Computation in Mathematics, vol.\u00a031. Springer, Cham (2024). https:\/\/doi.org\/10.1007\/978-3-031-47504-7","DOI":"10.1007\/978-3-031-47504-7"},{"key":"14_CR33","doi-asserted-by":"publisher","unstructured":"Maalouly, N.E., Steiner, R., Wulf, L.: Exact matching: correct parity and FPT parameterized by independence number. In: Proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a0283, pp. 28:1\u201328:18. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik (2023). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2023.28","DOI":"10.4230\/LIPIcs.ISAAC.2023.28"},{"key":"14_CR34","doi-asserted-by":"publisher","unstructured":"McCuaig, W.: P\u00f3lya\u2019s permanent problem. Electron. J. Comb. 11(1), Research Paper R79, 83 pp. (2004). https:\/\/doi.org\/10.37236\/1832","DOI":"10.37236\/1832"},{"issue":"1","key":"14_CR35","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02579224","volume":"7","author":"K Mulmuley","year":"1987","unstructured":"Mulmuley, K., Vazirani, U.V., Vazirani, V.V.: Matching is as easy as matrix inversion. Combinatorica 7(1), 105\u2013113 (1987). https:\/\/doi.org\/10.1007\/BF02579224","journal-title":"Combinatorica"},{"key":"14_CR36","doi-asserted-by":"publisher","unstructured":"N\u00e4gele, M., Santiago, R., Zenklusen, R.: Congruency-Constrained TU Problems Beyond the Bimodular Case, pp. 2743\u20132790. https:\/\/doi.org\/10.1137\/1.9781611977073.108","DOI":"10.1137\/1.9781611977073.108"},{"issue":"6","key":"14_CR37","doi-asserted-by":"publisher","first-page":"1351","DOI":"10.1007\/s00493-019-3900-1","volume":"39","author":"M N\u00e4gele","year":"2019","unstructured":"N\u00e4gele, M., Sudakov, B., Zenklusen, R.: Submodular minimization under congruency constraints. Combinatorica 39(6), 1351\u20131386 (2019). https:\/\/doi.org\/10.1007\/s00493-019-3900-1","journal-title":"Combinatorica"},{"issue":"2","key":"14_CR38","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-7","volume":"28","author":"CH Papadimitriou","year":"1984","unstructured":"Papadimitriou, C.H., Yannakakis, M.: The complexity of facets (and some facets of complexity). J. Comput. Syst. Sci. 28(2), 244\u2013259 (1984). https:\/\/doi.org\/10.1016\/0022-0000(84)90068-7","journal-title":"J. Comput. Syst. Sci."},{"key":"14_CR39","unstructured":"Plummer, M.D., Lov\u00e1sz, L.: Matching Theory, vol.\u00a029. Elsevier (1986)"},{"issue":"3","key":"14_CR40","doi-asserted-by":"publisher","first-page":"929","DOI":"10.2307\/121059","volume":"150","author":"N Robertson","year":"1999","unstructured":"Robertson, N., Seymour, P.D., Thomas, R.: Permanents, pfaffian orientations, and even directed circuits. Ann. Math. (2) 150(3), 929\u2013975 (1999). https:\/\/doi.org\/10.2307\/121059","journal-title":"Ann. Math. (2)"},{"issue":"2","key":"14_CR41","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/0012-365X(80)90057-6","volume":"32","author":"A Schrijver","year":"1980","unstructured":"Schrijver, A.: A counterexample to a conjecture of Edmonds and Giles. Discrete Math. 32(2), 213\u2013215 (1980). https:\/\/doi.org\/10.1016\/0012-365X(80)90057-6","journal-title":"Discrete Math."},{"key":"14_CR42","unstructured":"Schrijver, A.: Combinatorial Optimization. Polyhedra and Efficiency. Springer, Heidelberg (2003)"},{"key":"14_CR43","unstructured":"Schrijver, A.: Observations on Woodall\u2019s conjecture. https:\/\/homepages.cwi.nl\/~lex\/files\/woodall.pdf"},{"key":"14_CR44","doi-asserted-by":"publisher","first-page":"44","DOI":"10.4153\/CJM-1950-005-2","volume":"2","author":"WT Tutte","year":"1950","unstructured":"Tutte, W.T.: The factorization of locally finite graphs. Can. J. Math. 2, 44\u201349 (1950). https:\/\/doi.org\/10.4153\/CJM-1950-005-2","journal-title":"Can. J. Math."},{"key":"14_CR45","doi-asserted-by":"crossref","unstructured":"Woodall, D.: Menger and K\u00f6nig systems. In: Alavi, Y., Lick, D. (eds.) Theory and Applications of Graphs. Lecture Notes in Mathematics, vol.\u00a0642. Springer, Heidelberg (1978)","DOI":"10.1007\/BFb0070416"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-28691-8_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T22:35:39Z","timestamp":1781303739000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-28691-8_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032286901","9783032286918"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-28691-8_14","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":"13 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that\u00a0are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IPCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Integer Programming and Combinatorial Optimization","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Padua","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":"17 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ipco2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/events.math.unipd.it\/ipco2026\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}