{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T16:40:58Z","timestamp":1709656858891},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T00:00:00Z","timestamp":1596412800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T00:00:00Z","timestamp":1596412800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"ANR GraphEn","award":["ANR-15-CE40-0009"],"award-info":[{"award-number":["ANR-15-CE40-0009"]}]},{"name":"ANR DISTANCIA","award":["ANR-17-CE40-0015"],"award-info":[{"award-number":["ANR-17-CE40-0015"]}]},{"name":"ANR GATO","award":["ANR-16-CE40-0009-01"],"award-info":[{"award-number":["ANR-16-CE40-0009-01"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,12]]},"DOI":"10.1007\/s00453-020-00738-y","type":"journal-article","created":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T07:05:38Z","timestamp":1596438338000},"page":"3588-3603","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Enumerating k-Arc-Connected Orientations"],"prefix":"10.1007","volume":"82","author":[{"given":"Sarah","family":"Blind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kolja","family":"Knauer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petru","family":"Valicov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,8,3]]},"reference":[{"key":"738_CR1","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/978-3-030-30786-8_10","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"O Aichholzer","year":"2019","unstructured":"Aichholzer, O., Cardinal, J., Huynh, T., Knauer, K., M\u00fctze, T., Steiner, R., Vogtenhuber, B.: Flip distances between graph orientations. In: Sau, I., Thilikos, D.M. (eds.) Graph-Theoretic Concepts in Computer Science, pp. 120\u2013134. Springer, Cham (2019)"},{"issue":"3","key":"738_CR2","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1002\/jgt.22157","volume":"87","author":"J Bang-Jensen","year":"2018","unstructured":"Bang-Jensen, J., Huang, J., Zhu, X.: Completing orientations of partially oriented graphs. J. Graph Theory 87(3), 285\u2013304 (2018)","journal-title":"J. Graph Theory"},{"issue":"1","key":"738_CR3","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/S0020-0190(99)00120-9","volume":"72","author":"VC Barbosa","year":"1999","unstructured":"Barbosa, V.C., Szwarcfiter, J.L.: Generating all the acyclic orientations of an undirected graph. Inf. Process. Lett. 72(1), 71\u201374 (1999)","journal-title":"Inf. Process. Lett."},{"key":"738_CR4","unstructured":"Blind, S.: Output-sensitive algorithms for enumeration problems in graphs. Ph.D. thesis, Universit\u00e9 de Lorraine (2019)"},{"key":"738_CR5","unstructured":"Brehm, E.: 3-orientations and Schnyder-3-tree-decompositions. Diploma thesis, FU Berlin (2000)"},{"issue":"4","key":"738_CR6","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF01108825","volume":"10","author":"G Brightwell","year":"1993","unstructured":"Brightwell, G.: On the complexity of diagram testing. Order 10(4), 297\u2013303 (1993)","journal-title":"Order"},{"key":"738_CR7","unstructured":"Conte, A.: Enumeration algorithms for real-world networks: efficiency and beyond. Ph.D. thesis, Universit\u00e0 di Pisa (2018)"},{"key":"738_CR8","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/j.dam.2017.08.002","volume":"246","author":"A Conte","year":"2018","unstructured":"Conte, A., Grossi, R., Marino, A., Rizzi, R.: Efficient enumeration of graph orientations with sources. Discrete Appl. Math. 246, 22\u201337 (2018)","journal-title":"Discrete Appl. Math."},{"key":"738_CR9","first-page":"83","volume-title":"Directing Road Networks by Listing Strong Orientations","author":"A Conte","year":"2016","unstructured":"Conte, A., Grossi, R., Marino, A., Rizzi, R., Versari, L.: Directing Road Networks by Listing Strong Orientations, pp. 83\u201395. Springer, Berlin (2016)"},{"key":"738_CR10","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.dam.2019.02.025","volume":"268","author":"N Creignou","year":"2019","unstructured":"Creignou, N., Kr\u00f6ll, M., Pichler, R., Skritek, S., Vollmer, H.: A complexity theory for hard enumeration problems. Discrete Appl. Math. 268, 191\u2013209 (2019)","journal-title":"Discrete Appl. Math."},{"key":"738_CR11","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/j.jctb.2019.07.001","volume":"141","author":"OD de Gevigney","year":"2020","unstructured":"de Gevigney, O.D.: On Frank\u2019s conjecture on $$k$$-connected orientations. J. Combin. Theory Ser. B 141, 105\u2013114 (2020)","journal-title":"J. Combin. Theory Ser. B"},{"key":"738_CR12","first-page":"1277","volume":"11","author":"EA Dinits","year":"1970","unstructured":"Dinits, E.A.: Algorithm for solution of a problem of maximum flow in a network with power estimation. Sov. Math. Dokl. 11, 1277\u20131280 (1970)","journal-title":"Sov. Math. Dokl."},{"key":"738_CR13","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J Edmonds","year":"1972","unstructured":"Edmonds, J., Karp, R.M.: Theoretical improvements in algorithmic efficiency for network flow problems. J. Assoc. Comput. Mach. 19, 248\u2013264 (1972)","journal-title":"J. Assoc. Comput. Mach."},{"issue":"3","key":"738_CR14","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1145\/321765.321781","volume":"20","author":"G Ehrlich","year":"1973","unstructured":"Ehrlich, G.: Loopless algorithms for generating permutations, combinations, and other combinatorial configurations. J. ACM 20(3), 500\u2013513 (1973)","journal-title":"J. ACM"},{"key":"738_CR15","doi-asserted-by":"crossref","unstructured":"Felsner, S.: Lattice structures from planar graphs. Electron. J. Combin. 11(1) (2004). Research Paper 15","DOI":"10.37236\/1768"},{"key":"738_CR16","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/978-1-4614-0110-0_12","volume-title":"Thirty Essays on Geometric Graph Theory","author":"S Felsner","year":"2013","unstructured":"Felsner, S.: Rectangle and square representations of planar graphs. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 213\u2013248. Springer, New York (2013)"},{"key":"738_CR17","doi-asserted-by":"crossref","unstructured":"Felsner, S., Schrezenmaier, H., Steiner, R.: Pentagon contact representations. Electron. J. Combin. 25(3) (2018). Paper 3.39, 38","DOI":"10.37236\/7216"},{"key":"738_CR18","first-page":"97","volume":"16","author":"A Frank","year":"1982","unstructured":"Frank, A.: An algorithm for submodular functions on graphs. Ann. Discrete Math. 16, 97\u2013120 (1982)","journal-title":"Ann. Discrete Math."},{"issue":"1","key":"738_CR19","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/0012-365X(82)90044-9","volume":"39","author":"A Frank","year":"1982","unstructured":"Frank, A.: A note on $$k$$-strongly connected orientations of an undirected graph. Discrete Math. 39(1), 103\u2013104 (1982)","journal-title":"Discrete Math."},{"key":"738_CR20","unstructured":"Gabow, H.N.: A framework for cost-scaling algorithms for submodular flow problems. In: 34th Annual Symposium on Foundations of Computer Science, Palo Alto, USA, Nov 1993, pp. 449\u2013458 (1993)"},{"key":"738_CR21","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: Efficient splitting off algorithms for graphs. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, STOC \u201994, pp. 696\u2013705. ACM, New York (1994)","DOI":"10.1145\/195058.195436"},{"issue":"3","key":"738_CR22","doi-asserted-by":"crossref","first-page":"586","DOI":"10.1006\/jagm.1995.1022","volume":"18","author":"HN Gabow","year":"1995","unstructured":"Gabow, H.N.: Centroids, representations, and submodular flows. J. Algorithms 18(3), 586\u2013628 (1995)","journal-title":"J. Algorithms"},{"issue":"1","key":"738_CR23","first-page":"229","volume":"23","author":"PM Gilmer","year":"1986","unstructured":"Gilmer, P.M., Litherland, R.A.: The duality conjecture in formal knot theory. Osaka J. Math. 23(1), 229\u2013247 (1986)","journal-title":"Osaka J. Math."},{"issue":"2","key":"738_CR24","doi-asserted-by":"crossref","first-page":"241","DOI":"10.7151\/dmgt.1200","volume":"23","author":"PM Gleiss","year":"2003","unstructured":"Gleiss, P.M., Leydold, J., Stadler, P.F.: Circuit bases of strongly connected digraphs. Discuss. Math. Graph Theory 23(2), 241\u2013260 (2003)","journal-title":"Discuss. Math. Graph Theory"},{"key":"738_CR25","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0163-9","volume-title":"Algebraic Graph Theory","author":"C Godsil","year":"2001","unstructured":"Godsil, C., Royle, G.: Algebraic Graph Theory, vol. 207. Springer, New York (2001)"},{"issue":"1","key":"738_CR26","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/s00454-012-9400-1","volume":"48","author":"D Gon\u00e7alves","year":"2012","unstructured":"Gon\u00e7alves, D., L\u00e9v\u00eaque, B., Pinlou, A.: Triangle contact representations and duality. Discrete Comput. Geom. 48(1), 239\u2013254 (2012)","journal-title":"Discrete Comput. Geom."},{"issue":"2","key":"738_CR27","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/S0166-218X(00)00258-4","volume":"110","author":"M Habib","year":"2001","unstructured":"Habib, M., Medina, R., Nourine, L., Steiner, G.: Efficient algorithms on distributive lattices. Discrete Appl. Math. 110(2), 169\u2013187 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"738_CR28","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1007\/s00453-008-9179-x","volume":"56","author":"S Iwata","year":"2010","unstructured":"Iwata, S., Kobayashi, Y.: An algorithm for minimum cost arc-connectivity orientations. Algorithmica 56(4), 437\u2013447 (2010)","journal-title":"Algorithmica"},{"key":"738_CR29","doi-asserted-by":"crossref","DOI":"10.1515\/9783110617368","volume-title":"Algebraic Graph Theory. Morphisms, Monoids and Matrices","author":"U Knauer","year":"2019","unstructured":"Knauer, U., Knauer, K.: Algebraic Graph Theory. Morphisms, Monoids and Matrices, vol. 41, 2 revised and extended edn. De Gruyter, Berlin (2019)","edition":"2 revised and e"},{"issue":"1","key":"738_CR30","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1023\/A:1024483217354","volume":"20","author":"PCB Lam","year":"2003","unstructured":"Lam, P.C.B., Zhang, H.: A distributive lattice on the set of perfect matchings of a plane bipartite graph. Order 20(1), 13\u201329 (2003)","journal-title":"Order"},{"issue":"3","key":"738_CR31","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.1137\/100790239","volume":"42","author":"LC Lau","year":"2013","unstructured":"Lau, L.C., Yung, C.K.: Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities. SIAM J. Comput. 42(3), 1185\u20131200 (2013)","journal-title":"SIAM J. Comput."},{"key":"738_CR32","volume-title":"Combinatorial Problems and Exercises","author":"L Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz, L.: Combinatorial Problems and Exercises. North-Holland, Amsterdam (1979)"},{"issue":"1","key":"738_CR33","doi-asserted-by":"crossref","first-page":"96","DOI":"10.4064\/fm-10-1-96-115","volume":"10","author":"K Menger","year":"1927","unstructured":"Menger, K.: Zur allgemeinen Kurventheorie. Fundam. Math. 10(1), 96\u2013115 (1927)","journal-title":"Fundam. Math."},{"key":"738_CR34","doi-asserted-by":"crossref","first-page":"555","DOI":"10.4153\/CJM-1960-049-6","volume":"12","author":"CSJA Nash-Williams","year":"1960","unstructured":"Nash-Williams, C.S.J.A.: On orientations, connectivity and odd-vertex-pairings in finite graphs. Can. J. Math. 12, 555\u2013567 (1960)","journal-title":"Can. J. Math."},{"key":"738_CR35","unstructured":"Neumann-Lara, V.: Vertex colourings in digraphs, some problems. Technical report, Waterloo, Canada (1985)"},{"key":"738_CR36","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: Max flows in $$O(nm)$$ time, or better. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, STOC \u201913. Palo Alto, CA, USA, June 1\u20134, 2013, pp. 765\u2013774 (2013)","DOI":"10.1145\/2488608.2488705"},{"key":"738_CR37","unstructured":"Propp, J.: Lattice structure for orientations of graphs (2002). ArXiv:math\/0209005"},{"issue":"3","key":"738_CR38","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1007\/BF01110545","volume":"10","author":"G Pruesse","year":"1993","unstructured":"Pruesse, G., Ruskey, F.: Gray codes from antimatroids. Order 10(3), 239\u2013252 (1993)","journal-title":"Order"},{"issue":"2","key":"738_CR39","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1016\/j.tcs.2004.03.020","volume":"322","author":"E R\u00e9mila","year":"2004","unstructured":"R\u00e9mila, E.: The lattice structure of the set of domino tilings of a polygon. Theoret. Comput. Sci. 322(2), 409\u2013422 (2004)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"738_CR40","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1006\/jagm.1997.0891","volume":"26","author":"MB Squire","year":"1998","unstructured":"Squire, M.B.: Generating the acyclic orientations of a graph. J. Algorithms 26(2), 275\u2013290 (1998)","journal-title":"J. Algorithms"},{"key":"738_CR41","unstructured":"The Sage Developers. SageMath, the Sage Mathematics Software System (Version 9.1)"},{"key":"738_CR42","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/j.jctb.2014.07.004","volume":"110","author":"C Thomassen","year":"2015","unstructured":"Thomassen, C.: Strongly 2-connected orientations of graphs. J. Combin. Theory Ser. B 110, 67\u201378 (2015)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"8","key":"738_CR43","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1080\/00029890.1990.11995660","volume":"97","author":"WP Thurston","year":"1990","unstructured":"Thurston, W.P.: Conway\u2019s tiling groups. Am. Math. Mon. 97(8), 757\u2013773 (1990)","journal-title":"Am. Math. Mon."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00738-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00738-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00738-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,2]],"date-time":"2021-08-02T23:16:01Z","timestamp":1627946161000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00738-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,3]]},"references-count":43,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["738"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00738-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,8,3]]},"assertion":[{"value":"26 November 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}