{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T18:47:09Z","timestamp":1776106029030,"version":"3.50.1"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,3,21]],"date-time":"2009-03-21T00:00:00Z","timestamp":1237593600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,2]]},"DOI":"10.1007\/s00453-009-9299-y","type":"journal-article","created":{"date-parts":[[2009,3,20]],"date-time":"2009-03-20T14:28:44Z","timestamp":1237559324000},"page":"129-144","source":"Crossref","is-referenced-by-count":31,"title":["The Stackelberg Minimum Spanning Tree Game"],"prefix":"10.1007","volume":"59","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":"Stefan","family":"Langerman","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":[[2009,3,21]]},"reference":[{"issue":"1\u20132","key":"9299_CR1","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/S0304-3975(98)00158-3","volume":"237","author":"P. Alimonti","year":"2000","unstructured":"Alimonti, P., Kann, V.: Some APX-completeness results for cubic graphs. Theor. Comput. Sci. 237(1\u20132), 123\u2013134 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"9299_CR2","doi-asserted-by":"crossref","unstructured":"Balcan, M.-F., Blum, A.: Approximation algorithms and online mechanisms for item pricing. In: Proc. ACM Conference on Electronic Commerce (EC) (2006)","DOI":"10.1145\/1134707.1134711"},{"key":"9299_CR3","doi-asserted-by":"crossref","unstructured":"Balcan, M.-F., Blum, A., Manshour, Y.: Item pricing for revenue maximization. In: Proc. ACM Conference on Electronic Commerce (EC) (2008)","DOI":"10.1145\/1386790.1386802"},{"issue":"4","key":"9299_CR4","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1002\/nav.20216","volume":"54","author":"M. Bouhtou","year":"2007","unstructured":"Bouhtou, M., Grigoriev, A., van Hoesel, S., van der Kraaij, A.F., Spieksma, F.C.R., Uetz, M.: Pricing bridges to cross a river. Nav. Res. Logist. 54(4), 411\u2013420 (2007)","journal-title":"Nav. Res. Logist."},{"key":"9299_CR5","unstructured":"Briest, P., Hoefer, M., Krysta, P.: Stackelberg network pricing games. In: Proc. 25th International Symposium on Theoretical Aspects of Computer Science (STACS), pp.\u00a0133\u2013142 (2008)"},{"key":"9299_CR6","doi-asserted-by":"crossref","unstructured":"Briest, P., Krysta, P.: Single-minded unlimited supply pricing on sparse instances. In: Proc. 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a01093\u20131102 (2006)","DOI":"10.1145\/1109557.1109678"},{"key":"9299_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/978-3-540-73951-7_7","volume-title":"Proc. 10th International Workshop on Algorithms and Data Structures (WADS)","author":"J. Cardinal","year":"2007","unstructured":"Cardinal, J., Demaine, E.D., Fiorini, S., Joret, G., Langerman, S., Newman, I., Weimann, O.: The Stackelberg minimum spanning tree game. In: Proc. 10th International Workshop on Algorithms and Data Structures (WADS). Lecture Notes in Computer Science, vol.\u00a04619, pp.\u00a064\u201376. Springer, Berlin (2007)"},{"key":"9299_CR8","unstructured":"Cardinal, J., Labb\u00e9, M., Langerman, S., Palop, B.: Pricing of geometric transportation networks. In: Proc. Canadian Conference on Computational Geometry (CCCG), pp.\u00a092\u201396 (2005)"},{"key":"9299_CR9","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., Feige, U., Hajiaghayi, M., Salavatipour, M.R.: Combination can be hard: Approximability of the unique coverage problem. SIAM J. Comput. (2009, to appear)","DOI":"10.1137\/060656048"},{"key":"9299_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/11917496_12","volume-title":"Proc. Workshop on Graph-Theoretic Concepts in Computer Science (WG)","author":"A. Grigoriev","year":"2006","unstructured":"Grigoriev, A., van Loon, J., Sitters, R., Uetz, M.: How to sell a graph: Guidelines for graph retailers. In: Proc. Workshop on Graph-Theoretic Concepts in Computer Science (WG). Lecture Notes in Computer Science, vol.\u00a04271, pp.\u00a0125\u2013136. Springer, Berlin (2006)"},{"key":"9299_CR11","unstructured":"Guruswami, V., Hartline, J., Karlin, A., Kempe, D., Kenyon, C., McSherry, F.: On profit-maximizing envy-free pricing. In: Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\u00a01164\u20131173 (2005)"},{"key":"9299_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/11534273_37","volume-title":"Proc. Workshop on Algorithms and Data Structures (WADS)","author":"J.D. Hartline","year":"2005","unstructured":"Hartline, J.D., Koltun, V.: Near-optimal pricing in near-linear time. In: Proc. Workshop on Algorithms and Data Structures (WADS). Lecture Notes in Computer Science, vol.\u00a03608, pp.\u00a0422\u2013431. Springer, Berlin (2005)"},{"issue":"12","key":"9299_CR13","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.: A bilevel model of taxation and its application to optimal highway pricing. Manag. Sci. 44(12), 1608\u20131622 (1998)","journal-title":"Manag. Sci."},{"issue":"3","key":"9299_CR14","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9299_CR15","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.: An approximation algorithm for Stackelberg network pricing. Networks 46(1), 57\u201367 (2005)","journal-title":"Networks"},{"key":"9299_CR16","series-title":"Algorithms and Combinatorics","volume-title":"Combinatorial Optimization. Polyhedra and Efficiency, vol.\u00a0B","author":"A. Schrijver","year":"2003","unstructured":"Schrijver, A.: Matroids, trees, stable sets. In: Combinatorial Optimization. Polyhedra and Efficiency, vol.\u00a0B. Algorithms and Combinatorics, vol.\u00a024. Springer, Berlin (2003). Chaps.\u00a039\u201369"},{"key":"9299_CR17","unstructured":"van Hoesel, S.: An overview of Stackelberg pricing in networks. Research Memoranda 042, Maastricht: METEOR, Maastricht Research School of Economics of Technology and Organization (2006)"},{"key":"9299_CR18","volume-title":"Marktform und Gleichgewicht (Market and Equilibrium)","author":"H. Stackelberg von","year":"1934","unstructured":"von Stackelberg, H.: Marktform und Gleichgewicht (Market and Equilibrium). Springer, Vienna (1934)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9299-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9299-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9299-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:04Z","timestamp":1559137504000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9299-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3,21]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["9299"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9299-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3,21]]}}}