{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T06:26:41Z","timestamp":1773815201673,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2019,1,8]],"date-time":"2019-01-08T00:00:00Z","timestamp":1546905600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["LP2016-3\/2016"],"award-info":[{"award-number":["LP2016-3\/2016"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"OTKA","doi-asserted-by":"crossref","award":["K128611"],"award-info":[{"award-number":["K128611"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["Cooperation of Excellences Grant (KEP-6\/2018)"],"award-info":[{"award-number":["Cooperation of Excellences Grant (KEP-6\/2018)"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["J\u00e1nos Bolyai Research Fellowship"],"award-info":[{"award-number":["J\u00e1nos Bolyai Research Fellowship"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Ministry of Human Resources under its New National Excellence Programme","award":["UNKP-18-4-BME-331"],"award-info":[{"award-number":["UNKP-18-4-BME-331"]}]},{"DOI":"10.13039\/501100000921","name":"European Cooperation in Science and Technology","doi-asserted-by":"publisher","award":["IC1205 on Computational Social Choice"],"award-info":[{"award-number":["IC1205 on Computational Social Choice"]}],"id":[{"id":"10.13039\/501100000921","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","award":["German Federal Ministry of Education and Research (BMBF)"],"award-info":[{"award-number":["German Federal Ministry of Education and Research (BMBF)"]}],"id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,6]]},"DOI":"10.1007\/s00453-018-00544-7","type":"journal-article","created":{"date-parts":[[2019,1,9]],"date-time":"2019-01-09T02:16:52Z","timestamp":1547000212000},"page":"2557-2591","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["New and Simple Algorithms for Stable Flow Problems"],"prefix":"10.1007","volume":"81","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4991-2599","authenticated-orcid":false,"given":"\u00c1gnes","family":"Cseh","sequence":"first","affiliation":[]},{"given":"Jannik","family":"Matuschke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,1,8]]},"reference":[{"key":"544_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0166-218X(99)00203-6","volume":"101","author":"M Ba\u00efou","year":"2000","unstructured":"Ba\u00efou, M., Balinski, M.: Many-to-many matching: stable polyandrous polygamy (or polygamous polyandry). Discrete Appl. Math. 101, 1\u201312 (2000)","journal-title":"Discrete Appl. Math."},{"key":"544_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1006\/jeth.1998.2469","volume":"84","author":"M Balinski","year":"1999","unstructured":"Balinski, M., S\u00f6nmez, T.: A tale of two mechanisms: student placement. J. Econ. Theory 84, 73\u201394 (1999)","journal-title":"J. Econ. Theory"},{"key":"544_CR3","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/j.geb.2017.02.002","volume":"108","author":"P Bir\u00f3","year":"2017","unstructured":"Bir\u00f3, P., Kern, W., Paulusma, D., Wojuteczky, P.: The stable fixtures problem with payments. Games Econ. Behav. 108, 245\u2013268 (2017)","journal-title":"Games Econ. Behav."},{"key":"544_CR4","doi-asserted-by":"publisher","unstructured":"Braun, S., Dwenger, N., K\u00fcbler, D.: Telling the truth may not pay off: an empirical study of centralized university admissions in Germany. B.E. J. Econ. Anal. Policy (2010). https:\/\/doi.org\/10.2202\/1935-1682.2294","DOI":"10.2202\/1935-1682.2294"},{"key":"544_CR5","doi-asserted-by":"publisher","first-page":"1669","DOI":"10.1257\/000282802762024728","volume":"92","author":"Y Chen","year":"2002","unstructured":"Chen, Y., S\u00f6nmez, T.: Improving efficiency of on-campus housing: an experimental study. Am. Econ. Rev. 92, 1669\u20131686 (2002)","journal-title":"Am. Econ. Rev."},{"key":"544_CR6","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.disopt.2016.03.002","volume":"20","author":"\u00c1 Cseh","year":"2016","unstructured":"Cseh, \u00c1., Manlove, D.F.: Stable marriage and roommates problems with restricted edges: complexity and approximability. Discrete Optim. 20, 62\u201389 (2016)","journal-title":"Discrete Optim."},{"key":"544_CR7","doi-asserted-by":"publisher","first-page":"532","DOI":"10.3390\/a6030532","volume":"6","author":"\u00c1 Cseh","year":"2013","unstructured":"Cseh, \u00c1., Matuschke, J., Skutella, M.: Stable flows over time. Algorithms 6, 532\u2013545 (2013)","journal-title":"Algorithms"},{"key":"544_CR8","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00453-010-9416-y","volume":"58","author":"BC Dean","year":"2010","unstructured":"Dean, B.C., Munshi, S.: Faster algorithms for stable allocation problems. Algorithmica 58, 59\u201381 (2010)","journal-title":"Algorithmica"},{"key":"544_CR9","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1016\/S0304-3975(03)00319-0","volume":"306","author":"VMF Dias","year":"2003","unstructured":"Dias, V.M.F., da Fonseca, G.D., de Figueiredo, C.M.H., Szwarcfiter, J.L.: The stable marriage problem with restricted pairs. Theor. Comput. Sci. 306, 391\u2013405 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"544_CR10","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1016\/0022-0000(92)90048-N","volume":"45","author":"T Feder","year":"1992","unstructured":"Feder, T.: A new fixed point approach for stable networks and stable marriages. J. Comput. Syst. Sci. 45, 233\u2013284 (1992)","journal-title":"J. Comput. Syst. Sci."},{"key":"544_CR11","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF01240738","volume":"11","author":"T Feder","year":"1994","unstructured":"Feder, T.: Network flow and 2-satisfiability. Algorithmica 11, 291\u2013319 (1994)","journal-title":"Algorithmica"},{"key":"544_CR12","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/S0165-4896(03)00074-X","volume":"46","author":"T Fleiner","year":"2003","unstructured":"Fleiner, T.: On the stable $$b$$ b -matching polytope. Math. Soc. Sci. 46, 149\u2013158 (2003)","journal-title":"Math. Soc. Sci."},{"key":"544_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.3390\/a7010001","volume":"7","author":"T Fleiner","year":"2014","unstructured":"Fleiner, T.: On stable matchings and flows. Algorithms 7, 1\u201314 (2014)","journal-title":"Algorithms"},{"key":"544_CR14","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/j.tcs.2007.04.029","volume":"381","author":"T Fleiner","year":"2007","unstructured":"Fleiner, T., Irving, R.W., Manlove, D.F.: Efficient algorithms for generalised stable marriage and roommates problems. Theor. Comput. Sci. 381, 162\u2013176 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"544_CR15","doi-asserted-by":"crossref","unstructured":"Fleiner, T., Jagadeesan, R., Jank\u00f3, Z., Teytelboym, A.: Trading networks with frictions. In: Proceedings of the 2018 ACM Conference on Economics and Computation. ACM, pp. 615\u2013615 (2018)","DOI":"10.1145\/3219166.3219171"},{"key":"544_CR16","doi-asserted-by":"crossref","unstructured":"Fleiner, T., Jank\u00f3, Z., Schlotter, I., Teytelboym, A.: Complexity of stability in trading networks. arXiv preprint arXiv:1805.08758 (2018)","DOI":"10.1145\/3219166.3219171"},{"key":"544_CR17","doi-asserted-by":"crossref","DOI":"10.1515\/9781400875184","volume-title":"Flows in Networks","author":"LR Ford","year":"1962","unstructured":"Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)"},{"key":"544_CR18","doi-asserted-by":"crossref","unstructured":"Gai, A.T., Lebedev, D., Mathieu, F., de\u00a0Montgolfier, F., Reynier, J., Viennot, L.: Acyclic preference systems in P2P networks. In: Kermarrec, A., Boug\u00e9, L., Priol, T. (eds.) Proceedings of Euro-Par \u201907 (European Conference on Parallel and Distributed Computing): The 13th International Euro-Par Conference. Lecture Notes in Computer Science, vol. 4641, pp. 825\u2013834. Springer (2007)","DOI":"10.1007\/978-3-540-74466-5_88"},{"key":"544_CR19","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69, 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"key":"544_CR20","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0166-218X(85)90074-5","volume":"11","author":"D Gale","year":"1985","unstructured":"Gale, D., Sotomayor, M.: Some remarks on the stable matching problem. Discrete Appl. Math. 11, 223\u2013232 (1985)","journal-title":"Discrete Appl. Math."},{"key":"544_CR21","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. Freeman, San Francisco (1979)"},{"key":"544_CR22","volume-title":"The Stable Marriage Problem: Structure and Algorithms","author":"D Gusfield","year":"1989","unstructured":"Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)"},{"key":"544_CR23","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1145\/28869.28871","volume":"34","author":"RW Irving","year":"1987","unstructured":"Irving, R.W., Leather, P., Gusfield, D.: An efficient algorithm for the \u201coptimal\u201d stable marriage. J. ACM 34, 532\u2013543 (1987)","journal-title":"J. ACM"},{"key":"544_CR24","doi-asserted-by":"crossref","unstructured":"Jagadeesan, R.: Complementary inputs and the existence of stable outcomes in large trading networks. In: Proceedings of the 2017 ACM Conference on Economics and Computation. ACM, pp. 265\u2013265 (2017)","DOI":"10.1145\/3033274.3085113"},{"key":"544_CR25","volume-title":"Multi-commodity Network Solutions","author":"WS Jewell","year":"1966","unstructured":"Jewell, W.S.: Multi-commodity Network Solutions. Operations Research Center, University of California, California (1966)"},{"key":"544_CR26","doi-asserted-by":"publisher","first-page":"3327","DOI":"10.1016\/j.dam.2009.07.005","volume":"157","author":"T Kir\u00e1ly","year":"2009","unstructured":"Kir\u00e1ly, T., Pap, J.: A note on kernels and Sperner\u2019s Lemma. Discrete Appl. Math. 157, 3327\u20133331 (2009)","journal-title":"Discrete Appl. Math."},{"key":"544_CR27","doi-asserted-by":"publisher","first-page":"161","DOI":"10.3390\/a6010161","volume":"6","author":"T Kir\u00e1ly","year":"2013","unstructured":"Kir\u00e1ly, T., Pap, J.: Stable multicommodity flows. Algorithms 6, 161\u2013168 (2013). https:\/\/doi.org\/10.3390\/a6010161","journal-title":"Algorithms"},{"key":"544_CR28","doi-asserted-by":"crossref","unstructured":"Knuth, D.: Mariages Stables. Les Presses de L\u2019Universit\u00e9 de Montr\u00e9al (1976). In: English translation in Stable Marriage and its Relation to Other Combinatorial Problems, vol. 10 of CRM Proceedings and Lecture Notes, American Mathematical Society (1997)","DOI":"10.1090\/crmp\/010"},{"key":"544_CR29","unstructured":"Lin, Y.S., Nguyen, T.: On variants of network flow stability. arXiv preprint arXiv:1710.03091 (2017)"},{"key":"544_CR30","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1257\/aer.98.3.897","volume":"98","author":"M Ostrovsky","year":"2008","unstructured":"Ostrovsky, M.: Stability in supply chain networks. Am. Econ. Rev. 98, 897\u2013923 (2008)","journal-title":"Am. Econ. Rev."},{"key":"544_CR31","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48, 498\u2013532 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"544_CR32","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s00182-007-0083-4","volume":"36","author":"N Perach","year":"2008","unstructured":"Perach, N., Polak, J., Rothblum, U.G.: A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the Technion. Int. Jo. Game Theory 36, 519\u2013535 (2008)","journal-title":"Int. Jo. Game Theory"},{"key":"544_CR33","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1086\/261272","volume":"92","author":"AE Roth","year":"1984","unstructured":"Roth, A.E.: The evolution of the labor market for medical interns and residents: a case study in game theory. J. Polit. Econ. 92, 991\u20131016 (1984)","journal-title":"J. Polit. Econ."},{"key":"544_CR34","series-title":"Econometric Society Monographs","doi-asserted-by":"publisher","DOI":"10.1017\/CCOL052139015X","volume-title":"Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis","author":"AE Roth","year":"1990","unstructured":"Roth, A.E., Sotomayor, M.A.O.: Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Econometric Society Monographs, vol. 18. Cambridge University Press, Cambridge (1990)"},{"key":"544_CR35","doi-asserted-by":"crossref","unstructured":"Shepherd, F.B., Vetta, A., Wilfong, G.T.: Polylogarithmic approximations for the capacitated single-sink confluent flow problem. In: 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, pp. 748\u2013758 (2015)","DOI":"10.1109\/FOCS.2015.51"},{"key":"544_CR36","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1287\/opre.34.2.250","volume":"34","author":"\u00c9 Tardos","year":"1986","unstructured":"Tardos, \u00c9.: A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34, 250\u2013256 (1986)","journal-title":"Oper. Res."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00544-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-00544-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-00544-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,22]],"date-time":"2020-11-22T01:46:09Z","timestamp":1606009569000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-00544-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,8]]},"references-count":36,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2019,6]]}},"alternative-id":["544"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-00544-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,8]]},"assertion":[{"value":"19 July 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 December 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}