{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:48:40Z","timestamp":1758268120346,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,7,23]],"date-time":"2018-07-23T00:00:00Z","timestamp":1532304000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00453-018-0486-6","type":"journal-article","created":{"date-parts":[[2018,7,23]],"date-time":"2018-07-23T11:40:05Z","timestamp":1532346005000},"page":"1535-1560","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Polynomial-Time Algorithm for Detecting the Possibility of Braess Paradox in Directed Graphs"],"prefix":"10.1007","volume":"81","author":[{"given":"Pietro","family":"Cenciarelli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8859-9844","authenticated-orcid":false,"given":"Daniele","family":"Gorla","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3111-701X","authenticated-orcid":false,"given":"Ivano","family":"Salvo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,7,23]]},"reference":[{"key":"486_CR1","volume-title":"Studies in the Economics of Transportation","author":"M Beckmann","year":"1956","unstructured":"Beckmann, M., McGuire, C.B., Winsten, C.B.: Studies in the Economics of Transportation. Yale University Press, New Haven (1956)"},{"key":"486_CR2","volume-title":"Transportation Network Analysis","author":"M Bell","year":"1987","unstructured":"Bell, M., Iida, Y.: Transportation Network Analysis. Wiley, New York (1987)"},{"key":"486_CR3","first-page":"258","volume":"12","author":"D Braess","year":"1968","unstructured":"Braess, D.: \u00dcber ein paradoxon aus der verkehrsplannung. Unternehmensforschung 12, 258\u2013268 (1968)","journal-title":"Unternehmensforschung"},{"key":"486_CR4","unstructured":"Cenciarelli, P., Gorla, D., Salvo, I.: Depletable channels: dynamics, behaviour, and efficiency in network design. Submitted (An extended abstract appeared in Proceedings of FCT09, LNCS 5690, pp. 50\u201361 Springer) (2009). \n                    arXiv:1603.01983"},{"key":"486_CR5","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.ipl.2017.10.008","volume":"131","author":"P Cenciarelli","year":"2018","unstructured":"Cenciarelli, P., Gorla, D., Salvo, I.: Inefficiencies in network models: a graph\u2013theoretic perspective. Inf. Process. Lett. 131, 44\u201350 (2018)","journal-title":"Inf. Process. Lett."},{"key":"486_CR6","doi-asserted-by":"crossref","unstructured":"Chen, X., Diao, Z., Hu, X.: Excluding braess paradox in nonatomic selfish routing. In: Proceedings of SAGT15, vol. 9347 of LNCS, pp. 219\u2013230. Springer (2015)","DOI":"10.1007\/978-3-662-48433-3_17"},{"key":"486_CR7","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1007\/s00224-016-9710-4","volume":"59","author":"X Chen","year":"2016","unstructured":"Chen, X., Diao, Z., Hu, X.: Network characterizations for excluding Braess\u2019s paradox. Theory Comput. Syst. 59, 747\u2013780 (2016)","journal-title":"Theory Comput. Syst."},{"key":"486_CR8","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"RJ Duffin","year":"1965","unstructured":"Duffin, R.J.: Topology of series-parallel networks. J. Math. Anal. Appl. 10, 303\u2013318 (1965)","journal-title":"J. Math. Anal. Appl."},{"issue":"1","key":"486_CR9","doi-asserted-by":"publisher","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":"486_CR10","doi-asserted-by":"publisher","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":"486_CR11","unstructured":"Fujishige, S., Goemans, M., Harks, T., Peis, B., Zenklusen, R.: Matroids are immune to Braess paradox. (2015). \n                    arXiv:1504.07545"},{"key":"486_CR12","unstructured":"Granese, F.: Polynomially recognising graphs where saturating fiows are always maximum. B.Sc. Thesis, Sapienza University of Rome (2017). \n                    http:\/\/wwwusers.di.uniroma1.it\/~gorla\/papers\/granese.pdf\n                    \n                  . Accessed 2017"},{"key":"486_CR13","doi-asserted-by":"crossref","unstructured":"Hecht, M.S., Ullman, J.D.: Flow graph reducibility. In: Proceedings of STOC \u201972, pp. 238\u2013250. ACM Press (1972)","DOI":"10.1145\/800152.804919"},{"issue":"2","key":"486_CR14","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/S0165-4896(03)00076-3","volume":"46","author":"R Holzman","year":"2003","unstructured":"Holzman, R., Law-yone, N.: Network structure and strong equilibrium in route selection games. Math. Soc. Sci. 46(2), 193\u2013205 (2003)","journal-title":"Math. Soc. Sci."},{"issue":"3","key":"486_CR15","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1007\/s00182-014-0448-4","volume":"44","author":"R Holzman","year":"2015","unstructured":"Holzman, R., Monderer, D.: Strong equilibrium in network congestion games: increasing versus decreasing costs. Int. J. Game Theory 44(3), 647\u2013666 (2015)","journal-title":"Int. J. Game Theory"},{"issue":"2","key":"486_CR16","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0022-0000(80)90057-4","volume":"20","author":"AS LaPaugh","year":"1980","unstructured":"LaPaugh, A.S., Rivest, R.L.: The subgraph homeomorphism problem. J. Comput. Syst. Sci. 20(2), 133\u2013149 (1980)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"486_CR17","doi-asserted-by":"publisher","first-page":"1667","DOI":"10.1137\/090769600","volume":"25","author":"HC Lin","year":"2011","unstructured":"Lin, H.C., Roughgarden, T., Tardos, \u00c9., Walkover, A.: Stronger bounds on Braess\u2019s paradox and the maximum latency of selfish routing. SIAM J. Discrete Math. 25(4), 1667\u20131686 (2011)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"486_CR18","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01202792","volume":"13","author":"M Middendorf","year":"1993","unstructured":"Middendorf, M., Pfeiffer, F.: On the complexity of the disjoint paths problem. Combinatorica 13(1), 97\u2013107 (1993)","journal-title":"Combinatorica"},{"issue":"1","key":"486_CR19","doi-asserted-by":"publisher","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":"486_CR20","doi-asserted-by":"publisher","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, 321\u2013346 (2006)","journal-title":"Games Econ. Behav."},{"issue":"3","key":"486_CR21","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/s00182-014-0443-9","volume":"44","author":"I Milchtaich","year":"2015","unstructured":"Milchtaich, I.: Network topology and equilibrium existence in weighted network congestion games. Int. J. Game Theory 44(3), 515\u2013541 (2015)","journal-title":"Int. J. Game Theory"},{"key":"486_CR22","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1002\/sapm194221183","volume":"21","author":"J Riordan","year":"1942","unstructured":"Riordan, J., Shannon, C.: The number of two-terminal series-parallel networks. J. Math. Phys. 21, 83\u201393 (1942)","journal-title":"J. Math. Phys."},{"issue":"5","key":"486_CR23","doi-asserted-by":"publisher","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":"486_CR24","doi-asserted-by":"publisher","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"},{"key":"486_CR25","unstructured":"Schoenmakers, B.: A new algorithm for the recognition of series parallel graphs. Technical report, CWI\u2014Centrum voor Wiskunde en Informatica (1995)"},{"key":"486_CR26","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J Valdes","year":"1982","unstructured":"Valdes, J., Tarjan, R., Lawler, E.: The recognition of series-parallel digraphs. SIAM J. Comput. 11, 298\u2013313 (1982)","journal-title":"SIAM J. Comput."},{"key":"486_CR27","doi-asserted-by":"crossref","unstructured":"Wardrop, J.: Some theoretical aspects of road traffic research. In: Proceedings of the Institute of Civil Engineers, Pt. II, vol. 1, pp. 325\u2013378 (1952)","DOI":"10.1680\/ipeds.1952.11259"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0486-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-018-0486-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-018-0486-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,22]],"date-time":"2019-07-22T19:03:11Z","timestamp":1563822191000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-018-0486-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7,23]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["486"],"URL":"https:\/\/doi.org\/10.1007\/s00453-018-0486-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2018,7,23]]},"assertion":[{"value":"19 December 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 July 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 July 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}