{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:25Z","timestamp":1740109285394,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,7,31]],"date-time":"2019-07-31T00:00:00Z","timestamp":1564531200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,31]],"date-time":"2019-07-31T00:00:00Z","timestamp":1564531200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP16J06879"],"award-info":[{"award-number":["JP16J06879"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,4]]},"DOI":"10.1007\/s00453-019-00613-5","type":"journal-article","created":{"date-parts":[[2019,7,31]],"date-time":"2019-07-31T12:02:51Z","timestamp":1564574571000},"page":"787-807","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Making Bidirected Graphs Strongly Connected"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7677-0576","authenticated-orcid":false,"given":"Tatsuya","family":"Matsuoka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shun","family":"Sato","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,31]]},"reference":[{"key":"613_CR1","unstructured":"Ando, K., Fujishige, S.: $$\\sqcup $$,$$\\sqcap $$-closed families and signed posets. Discussion Paper Series 567, Institute of Socio-Economic Planning, University of Tsukuba (1994)"},{"key":"613_CR2","first-page":"293","volume":"74","author":"K Ando","year":"1996","unstructured":"Ando, K., Fujishige, S.: On structures of bisubmodular polyhedra. Math. Progr. 74, 293\u2013317 (1996)","journal-title":"Math. Progr."},{"key":"613_CR3","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0166-218X(95)00068-3","volume":"68","author":"K Ando","year":"1996","unstructured":"Ando, K., Fujishige, S., Nemoto, T.: Decomposition of a bidirected graph into strongly connected components and its signed poset structure. Discrete Appl. Math. 68, 237\u2013248 (1996)","journal-title":"Discrete Appl. Math."},{"key":"613_CR4","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/S0166-218X(01)00319-5","volume":"122","author":"EM Arkin","year":"2002","unstructured":"Arkin, E.M., Hassin, R., Shahar, S.: Increasing digraph arc-connectivity by arc addition, reversal and complement. Discrete Appl. Math. 122, 13\u201322 (2002)","journal-title":"Discrete Appl. Math."},{"key":"613_CR5","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/11753728_6","volume-title":"Computer Science \u2013 Theory and Applications","author":"Maxim A. Babenko","year":"2006","unstructured":"Babenko, M.A.: Acyclic bidirected and skew-symmetric graphs: algorithms and structure. In: International Computer Science Symposium in Russia, pp. 23\u201334. (2006)"},{"key":"613_CR6","doi-asserted-by":"publisher","first-page":"560","DOI":"10.1137\/16M1106717","volume":"32","author":"K B\u00e9rczi","year":"2018","unstructured":"B\u00e9rczi, K., Iwata, S., Kato, J., Yamaguchi, Y.: Making bipartite graphs DM-irreducible. SIAM J. Discrete Math. 32, 560\u2013590 (2018)","journal-title":"SIAM J. Discrete Math."},{"key":"613_CR7","unstructured":"Edmonds, J., Johnson, E. L.: Matching: a well-solved class of linear programs. In: Guy, R., Hanani, H., Sauer, N., Sch\u00f6nheim, J. (Eds.): Combinatorial Structures and Their Applications, pp. 88\u201392. (1970)"},{"key":"613_CR8","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1137\/0205044","volume":"5","author":"KP Eswaran","year":"1976","unstructured":"Eswaran, K.P., Tarjan, R.E.: Augmentation problems. SIAM J. Comput. 5, 653\u2013665 (1976)","journal-title":"SIAM J. Comput."},{"key":"613_CR9","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1137\/0405003","volume":"5","author":"A Frank","year":"1992","unstructured":"Frank, A.: Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discrete Math. 5, 25\u201353 (1992)","journal-title":"SIAM J. Discrete Math."},{"key":"613_CR10","first-page":"155","volume-title":"Lecture Notes in Computer Science","author":"Andrew V. Goldberg","year":"1995","unstructured":"Goldberg, A.V., Karzanov, A.V.: Maximum skew-symmetric flows. In: Proceedings of the Third Annual European Symposium on Algorithms, pp. 155\u2013170. (1995)"},{"key":"613_CR11","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/BF01261321","volume":"16","author":"AV Goldberg","year":"1996","unstructured":"Goldberg, A.V., Karzanov, A.V.: Path problems in skew-symmetric graphs. Combinatorica 16, 353\u2013382 (1996)","journal-title":"Combinatorica"},{"key":"613_CR12","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1007\/s10107-004-0505-z","volume":"100","author":"AV Goldberg","year":"2004","unstructured":"Goldberg, A.V., Karzanov, A.V.: Maximum skew-symmetric flows and matchings. Math. Program. 100, 537\u2013568 (2004)","journal-title":"Math. Program."},{"key":"613_CR13","first-page":"143","volume":"2","author":"F Harary","year":"1955","unstructured":"Harary, F.: On the notion of balance of a signed graph. Michigan Math. J. 2, 143\u2013146 (1955)","journal-title":"Michigan Math. J."},{"key":"613_CR14","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/S0024-3795(97)00375-3","volume":"273","author":"S Iwata","year":"1998","unstructured":"Iwata, S.: Block triangularization of skew-symmetric matrices. Linear Algebra Appl. 273, 215\u2013226 (1998)","journal-title":"Linear Algebra Appl."},{"key":"613_CR15","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"Richard M. Karp","year":"1972","unstructured":"Karp, R. M.: Reducibility among combinatorial problems. In: Miller, R. E., Thatcher, J. W. (Eds.): Complexity of Computer Computations, pp. 85\u2013103. (1972)"},{"key":"613_CR16","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.1089\/cmb.2009.0047","volume":"16","author":"P Medvedev","year":"2009","unstructured":"Medvedev, P., Brudno, M.: Maximum likelihood genome assembly. J. Comput. Biol. 16, 1101\u20131116 (2009)","journal-title":"J. Comput. Biol."},{"key":"613_CR17","doi-asserted-by":"crossref","unstructured":"Medvedev, P., Georgiou, K., Myers, G., Brudno, M.: Computability of models for sequence assembly. Algorithms in Bioinformatics, pp. 289\u2013301. (2007)","DOI":"10.1007\/978-3-540-74126-8_27"},{"key":"613_CR18","doi-asserted-by":"publisher","first-page":"1101","DOI":"10.4153\/CJM-1967-101-8","volume":"19","author":"WT Tutte","year":"1967","unstructured":"Tutte, W.T.: Antisymmetrical digraphs. Can. J. Math. 19, 1101\u20131117 (1967)","journal-title":"Can. J. Math."},{"key":"613_CR19","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/0022-0000(87)90038-9","volume":"35","author":"T Watanabe","year":"1987","unstructured":"Watanabe, T., Nakamura, A.: Edge-connectivity augmentation problems. J. Comput. Syst. Sci. 35, 96\u2013144 (1987)","journal-title":"J. Comput. Syst. Sci."},{"key":"613_CR20","unstructured":"Yasuda, T.: Inferring chromosome structures with bidirected graphs constructed from genomic structural variations. Ph.D. Thesis, The University of Tokyo (2015)"},{"key":"613_CR21","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/S0195-6698(13)80118-7","volume":"12","author":"T Zaslavsky","year":"1991","unstructured":"Zaslavsky, T.: Orientation of signed graphs. Eur. J. Comb. 12, 361\u2013375 (1991)","journal-title":"Eur. J. Comb."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00613-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00613-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00613-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,29]],"date-time":"2020-07-29T23:19:08Z","timestamp":1596064748000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00613-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,31]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,4]]}},"alternative-id":["613"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00613-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2019,7,31]]},"assertion":[{"value":"30 August 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}