{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T06:56:33Z","timestamp":1763535393812,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,10,14]],"date-time":"2016-10-14T00:00:00Z","timestamp":1476403200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11222109","11531014"],"award-info":[{"award-number":["11222109","11531014"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,11]]},"DOI":"10.1007\/s00224-016-9710-4","type":"journal-article","created":{"date-parts":[[2016,10,14]],"date-time":"2016-10-14T02:58:47Z","timestamp":1476413927000},"page":"747-780","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["Network Characterizations for Excluding Braess\u2019s Paradox"],"prefix":"10.1007","volume":"59","author":[{"given":"Xujin","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhuo","family":"Diao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaodong","family":"Hu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,10,14]]},"reference":[{"key":"9710_CR1","doi-asserted-by":"crossref","unstructured":"Azar, Y., Epstein, A.: The hardness of network design for unsplittable flow with selfish users. In: Erlebach, T., Persinao, G. (eds.) Approximation and Online Algorithms, Lecture Notes in Computer Science, vol. 3879, pp. 41\u201354. Springer Berlin Heidelberg (2006)","DOI":"10.1007\/11671411_4"},{"key":"9710_CR2","unstructured":"Beckmann, M., McGuire, B., Winsten, C.B: Studies in the Economics of Transportation. Technical report (1956)"},{"key":"9710_CR3","doi-asserted-by":"crossref","unstructured":"Bell, M.G.H., Iida, Y.: Transportation Network Analysis (1997)","DOI":"10.1002\/9781118903032"},{"issue":"1","key":"9710_CR4","first-page":"258","volume":"12","author":"D Braess","year":"1968","unstructured":"Braess, D.: \u00dcber ein paradoxon aus der verkehrsplanung. Unternehmensforschung 12(1), 258\u2013268 (1968)","journal-title":"Unternehmensforschung"},{"key":"9710_CR5","unstructured":"Cenciarelli, P., Gorla, D., Salvo, I.: Graph theoretic investigations on inefficiencies in network models. Discret. Math. (2016). arXiv: 1603.01983"},{"key":"9710_CR6","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1038\/352699a0","volume":"352","author":"JE Cohen","year":"1991","unstructured":"Cohen, J.E., Horowitz, P.: Paradoxical behaviour of mechanical and electrical networks. Nature 352, 699\u2013701 (1991)","journal-title":"Nature"},{"key":"9710_CR7","doi-asserted-by":"crossref","unstructured":"Cygan, M., Marx, D., Pilipczuk, M.: The planar directed k-vertex-disjoint paths problem is fixed-parameter tractable. In: IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), 2013, pp. 197\u2013206. IEEE (2013)","DOI":"10.1109\/FOCS.2013.29"},{"key":"9710_CR8","unstructured":"Czumaj, A.: Selfish routing on the internet. In: Leung, J.Y.-T. (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, chap. 42. CRC Press (2004)"},{"key":"9710_CR9","unstructured":"Diestel, R.: Graph Theory. Electronic Library of Mathematics. Springer (2000)"},{"issue":"1","key":"9710_CR10","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.geb.2008.04.011","volume":"66","author":"A Epstein","year":"2009","unstructured":"Epstein, A., Feldman, M., Mansour, Y.: Efficient graph topologies in network routing games. Games Econ. Behav. 66(1), 115\u2013125 (2009)","journal-title":"Games Econ. Behav."},{"issue":"2","key":"9710_CR11","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10(2), 111\u2013121 (1980)","journal-title":"Theor. Comput. Sci."},{"key":"9710_CR12","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/j.tcs.2013.11.035","volume":"521","author":"D Fotakis","year":"2014","unstructured":"Fotakis, D., Kaporis, A.C., Lianeas, T., Spirakis, P.G.: On the hardness of network design for bottleneck routing games. Theor. Comput. Sci. 521, 107\u2013122 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"9710_CR13","unstructured":"Fujishige, S., Goemans, M.X., Harks, T., Peis, B., Zenklusen, R.: Matroids are immune to Braess paradox. Computer Science and Game Theory (2015). arXiv: 1504.07545v1"},{"key":"9710_CR14","doi-asserted-by":"crossref","unstructured":"Holzman, R., Monderer, D.: Strong equilibrium in network congestion games: Increasing versus decreasing costs. Int. J. Game Theory 1\u201320 (2014)","DOI":"10.1007\/s00182-014-0448-4"},{"issue":"2","key":"9710_CR15","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/S0165-4896(03)00076-3","volume":"46","author":"R Holzman","year":"2003","unstructured":"Holzman, R., Nissan Law yon (Lev-tov): Network structure and strong equilibrium in route selection games. Math. Soc. Sci. 46(2), 193\u2013205 (2003)","journal-title":"Math. Soc. Sci."},{"key":"9710_CR16","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.cosrev.2009.04.003","volume":"3","author":"E Koutsoupias","year":"2009","unstructured":"Koutsoupias, E., Papadimitriou, C.: Worst-case equilibria. Comput. Sci. Rev. 3, 65\u201369 (2009)","journal-title":"Comput. Sci. Rev."},{"issue":"4","key":"9710_CR17","doi-asserted-by":"crossref","first-page":"1667","DOI":"10.1137\/090769600","volume":"25","author":"H Lin","year":"2011","unstructured":"Lin, H., Roughgarden, T., Tardos, \u00c9., Walkover, A.: Stronger bounds on Braess\u2019s paradox and the maximum latency of selfish routing. SIAM J. Discret. Math. 25(4), 1667\u20131686 (2011)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"9710_CR18","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1287\/moor.1040.0122","volume":"30","author":"I Milchtaich","year":"2005","unstructured":"Milchtaich, I.: Topological conditions for uniqueness of equilibrium in networks. Math. Oper. Res. 30(1), 225\u2013244 (2005)","journal-title":"Math. Oper. Res."},{"key":"9710_CR19","doi-asserted-by":"crossref","unstructured":"Milchtaich, I.: The equilibrium existence problem in finite network congestion games. In: Spirakis, P., Mavronicolas, M., Kontogiannis, S. (eds.) Internet and Network Economics, Lecture Notes in Computer Science, vol. 4286, pp. 87\u201398. Springer Berlin Heidelberg (2006)","DOI":"10.1007\/11944874_9"},{"issue":"2","key":"9710_CR20","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/j.geb.2005.09.005","volume":"57","author":"I Milchtaich","year":"2006","unstructured":"Milchtaich, I.: Network topology and the efficiency of equilibrium. Games Econ. Behav. 57(2), 321\u2013346 (2006)","journal-title":"Games Econ. Behav."},{"issue":"4","key":"9710_CR21","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/0041-1647(70)90196-6","volume":"4","author":"D John","year":"1970","unstructured":"John, D.: Murchland. Braess\u2019s paradox of traffic flow. Transp. Res. 4(4), 391\u2013394 (1970)","journal-title":"Transp. Res."},{"issue":"5","key":"9710_CR22","doi-asserted-by":"crossref","first-page":"922","DOI":"10.1016\/j.jcss.2005.05.009","volume":"72","author":"T Roughgarden","year":"2006","unstructured":"Roughgarden, T.: On the severity of Braess\u2019s paradox: Designing networks for selfish users is hard. J. Comput. Syst. Sci. 72(5), 922\u2013953 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"9710_CR23","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1145\/506147.506153","volume":"49","author":"T Roughgarden","year":"2002","unstructured":"Roughgarden, T., Tardos, \u00c9.: How bad is selfish routing? J. ACM 49(2), 236\u2013259 (2002)","journal-title":"J. ACM"},{"issue":"4","key":"9710_CR24","doi-asserted-by":"crossref","first-page":"780","DOI":"10.1137\/S0097539792224061","volume":"23","author":"A Schrijver","year":"1994","unstructured":"Schrijver, A.: Finding k disjoint paths in a directed planar graph. SIAM J. Comput. 23(4), 780\u2013788 (1994)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9710_CR25","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1287\/trsc.17.3.301","volume":"17","author":"R Steinberg","year":"1983","unstructured":"Steinberg, R., Zangwill, W.I.: The prevalence of Braess\u2019 paradox. Transp. Sci. 17(3), 301\u2013318 (1983)","journal-title":"Transp. Sci."},{"key":"9710_CR26","unstructured":"Tutte, W.T.: Graph Theory. Electronic Library of Mathematics. China Machine Press (2004)"},{"issue":"2","key":"9710_CR27","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J Valdes","year":"1982","unstructured":"Valdes, J., Tarjan, R.E., Lawler, E.L.: The recognition of series parallel digraphs. SIAM J. Comput. 11(2), 298\u2013313 (1982)","journal-title":"SIAM J. Comput."},{"key":"9710_CR28","doi-asserted-by":"crossref","unstructured":"Wardrop, J.G.: Some theoretical aspects of road traffic research. In: Proceedings of the Institute of Civil Engineers, Part II, vol. 1, pp. 325\u2013378 (1952)","DOI":"10.1680\/ipeds.1952.11362"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9710-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9710-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9710-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,14]],"date-time":"2019-09-14T11:53:31Z","timestamp":1568462011000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9710-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,14]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,11]]}},"alternative-id":["9710"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9710-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2016,10,14]]}}}