{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:16:53Z","timestamp":1759637813342},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2011,10,7]],"date-time":"2011-10-07T00:00:00Z","timestamp":1317945600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2013,1]]},"DOI":"10.1007\/s10878-011-9414-2","type":"journal-article","created":{"date-parts":[[2011,10,6]],"date-time":"2011-10-06T15:49:58Z","timestamp":1317916198000},"page":"19-46","source":"Crossref","is-referenced-by-count":10,"title":["The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs"],"prefix":"10.1007","volume":"25","author":[{"given":"Jean","family":"Cardinal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erik D.","family":"Demaine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Samuel","family":"Fiorini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ilan","family":"Newman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oren","family":"Weimann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,10,7]]},"reference":[{"key":"9414_CR1","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1090\/conm\/147\/01199","volume-title":"Graph structure theory","author":"KR Abrahamson","year":"1993","unstructured":"Abrahamson KR, Fellows MR (1993) Finite automata, bounded treewidth, and well-quasiordering. In: Robertson N, Seymour P (eds) Graph structure theory, pp 539\u2013564"},{"issue":"1","key":"9414_CR2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"BS Baker","year":"1994","unstructured":"Baker BS (1994) Approximation algorithms for NP-complete problems on planar graphs. J ACM 41(1):153\u2013180","journal-title":"J ACM"},{"key":"9414_CR3","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1007\/978-3-642-17572-5_37","volume-title":"Proc 6th workshop on internet and network economics (WINE)","author":"P Briest","year":"2010","unstructured":"Briest P, Chalermsook P, Khanna S, Laekhanukit B, Nanongkai D (2010) Improved hardness of approximation for Stackelberg shortest-path pricing. In: Proc 6th workshop on internet and network economics (WINE), pp 444\u2013454"},{"key":"9414_CR4","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-3-642-17572-5_7","volume-title":"Proc 6th workshop on internet & network economics (WINE)","author":"D Bil\u00f2","year":"2010","unstructured":"Bil\u00f2 D, Gual\u00e0 L, Leucci S, Proietti G (2010) Specializations and generalizations of the Stackelberg minimum spanning tree game. In: Proc 6th workshop on internet & network economics (WINE), pp 75\u201386"},{"key":"9414_CR5","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/978-3-540-92185-1_32","volume-title":"Proc 4th workshop on internet and network economics (WINE)","author":"D Bil\u00f2","year":"2008","unstructured":"Bil\u00f2 D, Gual\u00e0 L, Proietti G, Widmayer P (2008) Computational aspects of a 2-player Stackelberg shortest paths tree game. In: Proc 4th workshop on internet and network economics (WINE), pp 251\u2013262"},{"key":"9414_CR6","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1007\/978-3-642-10841-9_6","volume-title":"Proc 5th workshop on internet and network economics (WINE)","author":"P Briest","year":"2009","unstructured":"Briest P, Hoefer M, Gual\u00e0 L, Ventre C (2009) On Stackelberg pricing with computationally bounded consumers. In: Proc 5th workshop on internet and network economics (WINE), pp 42\u201354"},{"key":"9414_CR7","first-page":"133","volume-title":"Proc 25th international symposium on theoretical aspects of computer science (STACS)","author":"P Briest","year":"2008","unstructured":"Briest P, Hoefer M, Krysta P (2008) Stackelberg network pricing games. In: Proc 25th international symposium on theoretical aspects of computer science (STACS), pp 133\u2013142"},{"issue":"3","key":"9414_CR8","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender HL, Koster AMCA (2008) Combinatorial optimization on graphs of bounded treewidth. Comput J 51(3):255\u2013269","journal-title":"Comput J"},{"key":"9414_CR9","volume-title":"Proc 18th annual ACM-SIAM symposium on discrete algorithms (SODA)","author":"G Borradaile","year":"2007","unstructured":"Borradaile G, Kenyon-Mathieu C, Klein PN (2007) A polynomial-time approximation scheme for Steiner tree in planar graphs. In: Proc 18th annual ACM-SIAM symposium on discrete algorithms (SODA)"},{"issue":"3","key":"9414_CR10","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1287\/trsc.34.3.289.12299","volume":"34","author":"L Brotcorne","year":"2000","unstructured":"Brotcorne L, Labb\u00e9 M, Marcotte P, Savard G (2000) A bilevel model and solution algorithm for a freight tariff-setting problem. Transp Sci 34(3):289\u2013302","journal-title":"Transp Sci"},{"issue":"4","key":"9414_CR11","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1287\/trsc.35.4.345.10433","volume":"35","author":"L Brotcorne","year":"2001","unstructured":"Brotcorne L, Labb\u00e9 M, Marcotte P, Savard G (2001) A bilevel model for toll optimization on a multicommodity transportation network. Transp Sci 35(4):345\u2013358","journal-title":"Transp Sci"},{"key":"9414_CR12","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender HL (1996) A linear time algorithm for finding tree-decompositions of small treewidth. SIAM J Comput 25:1305\u20131317","journal-title":"SIAM J Comput"},{"key":"9414_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/11917496_1","volume-title":"Proc 32nd international workshop on graph-theoretic concepts in computer science (WG)","author":"HL Bodlaender","year":"2006","unstructured":"Bodlaender HL (2006) Treewidth: Characterizations, applications, and computations. In: Proc 32nd international workshop on graph-theoretic concepts in computer science (WG), pp 1\u201314"},{"key":"9414_CR14","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/978-3-642-10841-9_13","volume-title":"Proc 5th workshop on internet & network economics (WINE)","author":"J Cardinal","year":"2009","unstructured":"Cardinal J, Demaine ED, Fiorini S, Joret G, Newman I, Weimann O (2009) The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs. In: Proc 5th workshop on internet & network economics (WINE), pp 125\u2013136"},{"issue":"2","key":"9414_CR15","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/s00453-009-9299-y","volume":"59","author":"J Cardinal","year":"2011","unstructured":"Cardinal J, Demaine ED, Fiorini S, Joret G, Langerman S, Newman I, Weimann O (2011) The Stackelberg minimum spanning tree game. Algorithmica 59(2):129\u2013144","journal-title":"Algorithmica"},{"key":"9414_CR16","series-title":"Lecture notes in computer science","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-540-70575-8_1","volume-title":"Proc international conference on automata, languages, and programming (ICALP)","author":"B Courcelle","year":"2008","unstructured":"Courcelle B (2008) Graph structure and monadic second-order logic: Language theoretical aspects. In: Proc international conference on automata, languages, and programming (ICALP). Lecture notes in computer science, vol\u00a05125. Springer, Berlin, pp\u00a01\u201313"},{"key":"9414_CR17","volume-title":"Proc 36th international colloquium on automata, languages and programming (ICALP)","author":"ED Demaine","year":"2009","unstructured":"Demaine ED, Hajiaghayi M, Kawarabayashi K (2009) Approximation algorithms via structural results for apex-minor-free graphs. In: Proc 36th international colloquium on automata, languages and programming (ICALP)"},{"key":"9414_CR18","first-page":"278","volume-title":"Proc 18th annual ACM-SIAM symposium on discrete algorithms (SODA)","author":"ED Demaine","year":"2007","unstructured":"Demaine ED, Hajiaghayi M, Mohar B (2007) Approximation algorithms via contraction decomposition. In: Proc 18th annual ACM-SIAM symposium on discrete algorithms (SODA), pp 278\u2013287"},{"key":"9414_CR19","series-title":"Graduate texts in mathematics","volume-title":"Graph theory","author":"R Diestel","year":"2005","unstructured":"Diestel R (2005) Graph theory. Graduate texts in mathematics, vol\u00a0173. Springer, Berlin, 3rd edn","edition":"3"},{"key":"9414_CR20","volume-title":"Computers and intractability, a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability, a guide to the theory of NP-completeness. Freeman, New York"},{"key":"9414_CR21","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1007\/978-3-540-31833-0_13","volume-title":"Proc workshop on approximation and online algorithms (WAOA)","author":"A Grigoriev","year":"2005","unstructured":"Grigoriev A, van Hoesel S, van\u00a0der Kraaij A, Uetz M, Bouhtou M (2005) Pricing network edges to cross a river. In: Proc workshop on approximation and online algorithms (WAOA), pp 140\u2013153"},{"issue":"1","key":"9414_CR22","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1002\/net.20260","volume":"53","author":"A Grigoriev","year":"2009","unstructured":"Grigoriev A, van Loon J, Sitters R, Uetz M (2009) Optimal pricing of capacitated networks. Networks 53(1):79\u201387","journal-title":"Networks"},{"key":"9414_CR23","first-page":"146","volume-title":"Proc 46th IEEE symposium on foundations of computer science (FOCS)","author":"PN Klein","year":"2005","unstructured":"Klein PN (2005) A linear-time approximation scheme for TSP for planar weighted graphs. In: Proc 46th IEEE symposium on foundations of computer science (FOCS), pp 146\u2013155"},{"key":"9414_CR24","first-page":"749","volume-title":"Proc 38th ACM symposium on theory of computing (STOC)","author":"PN Klein","year":"2006","unstructured":"Klein PN (2006) A subset spanner for planar graphs, with application to subset TSP. In: Proc 38th ACM symposium on theory of computing (STOC), pp 749\u2013756"},{"issue":"12","key":"9414_CR25","doi-asserted-by":"crossref","first-page":"1608","DOI":"10.1287\/mnsc.44.12.1608","volume":"44","author":"M Labb\u00e9","year":"1998","unstructured":"Labb\u00e9 M, Marcotte P, Savard G (1998) A bilevel model of taxation and its application to optimal highway pricing. Manag Sci 44(12):1608\u20131622","journal-title":"Manag Sci"},{"issue":"1","key":"9414_CR26","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1002\/net.20074","volume":"46","author":"S Roch","year":"2005","unstructured":"Roch S, Savard G, Marcotte P (2005) An approximation algorithm for Stackelberg network pricing. Networks 46(1):57\u201367","journal-title":"Networks"},{"key":"9414_CR27","unstructured":"van Hoesel S (2006) An overview of Stackelberg pricing in networks. Research memoranda 042, Maastricht: METEOR, Maastricht Research School of Economics of Technology and Organization"},{"key":"9414_CR28","volume-title":"Marktform und Gleichgewicht (Market and Equilibrium)","author":"H Stackelberg von","year":"1934","unstructured":"von Stackelberg H (1934) Marktform und Gleichgewicht (Market and Equilibrium). Springer, Vienna"},{"issue":"2","key":"9414_CR29","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J Valdes","year":"1982","unstructured":"Valdes J, Tarjan RE, Lawler EL (1982) The recognition of series parallel digraphs. SIAM J Comput 11(2):298\u2013313","journal-title":"SIAM J Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-011-9414-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-011-9414-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-011-9414-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T04:23:16Z","timestamp":1559276596000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-011-9414-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10,7]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["9414"],"URL":"https:\/\/doi.org\/10.1007\/s10878-011-9414-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10,7]]}}}