{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:10:55Z","timestamp":1725567055239},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540280613"},{"type":"electronic","value":"9783540318064"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11533719_40","type":"book-chapter","created":{"date-parts":[[2005,9,27]],"date-time":"2005-09-27T09:34:13Z","timestamp":1127813653000},"page":"390-400","source":"Crossref","is-referenced-by-count":8,"title":["A Truthful (2\u20132\/k)-Approximation Mechanism for the Steiner Tree Problem with k Terminals"],"prefix":"10.1007","author":[{"given":"Luciano","family":"Gual\u00e0","sequence":"first","affiliation":[]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"40_CR1","unstructured":"Archer, A., Tardos, \u00c9.: Frugal path mechanisms. In: Proc. of the 13th Annual ACMSIAM Symp. on Discrete Algorithms (SODA 2002), pp. 991\u2013999 (2002)"},{"key":"40_CR2","doi-asserted-by":"crossref","unstructured":"Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.: Linear-time pointermachine algorithms for least common ancestors, MST verification, and dominators. In: Proc. of the 30th Annual ACM Symposium on Theory of Computing (STOC 1998), pp. 279\u2013288 (1998)","DOI":"10.1145\/276698.276764"},{"key":"40_CR3","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.1145\/355541.355562","volume":"47","author":"B. Chazelle","year":"2000","unstructured":"Chazelle, B.: A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. of the ACM\u00a047, 1028\u20131047 (2000)","journal-title":"J. of the ACM"},{"key":"40_CR4","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF01726210","volume":"8","author":"E. Clarke","year":"1971","unstructured":"Clarke, E.: Multipart pricing of public goods. Public Choice\u00a08, 17\u201333 (1971)","journal-title":"Public Choice"},{"issue":"4","key":"40_CR5","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1145\/601819.601830","volume":"33","author":"J. Feigenbaum","year":"2002","unstructured":"Feigenbaum, J., Shenker, S.: Incentives and Internet computation. ACM SIGACT News\u00a033(4), 37\u201354 (2002)","journal-title":"ACM SIGACT News"},{"key":"40_CR6","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math.\u00a032, 826\u2013834 (1977)","journal-title":"SIAM J. Appl. Math."},{"issue":"2","key":"40_CR7","doi-asserted-by":"publisher","first-page":"427","DOI":"10.2307\/1911219","volume":"45","author":"J. Green","year":"1977","unstructured":"Green, J., Laffont, J.-J.: Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica\u00a045(2), 427\u2013438 (1977)","journal-title":"Econometrica"},{"issue":"4","key":"40_CR8","doi-asserted-by":"publisher","first-page":"617","DOI":"10.2307\/1914085","volume":"41","author":"T. Groves","year":"1973","unstructured":"Groves, T.: Incentives in teams. Econometrica\u00a041(4), 617\u2013631 (1973)","journal-title":"Econometrica"},{"key":"40_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"941","DOI":"10.1007\/11549468_103","volume-title":"Euro-Par 2005 Parallel Processing","author":"L. Gual\u00e0","year":"2005","unstructured":"Gual\u00e0, L., Proietti, G.: Efficient truthful mechanisms for the single-source shortest paths tree problem. In: Cunha, J.C., Medeiros, P.D. (eds.) Euro-Par 2005. LNCS, vol.\u00a03648, pp. 941\u2013951. Springer, Heidelberg (2005)"},{"key":"40_CR10","doi-asserted-by":"crossref","unstructured":"Hershberger, J., Suri, S.: Vickrey prices and shortest paths: what is an edge worth? In: Proc. of the 42nd Annual Symposium on Foundations of Computer Science (FOCS 2001), pp. 252\u2013259 (2001)","DOI":"10.1109\/SFCS.2001.959899"},{"key":"40_CR11","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0167-6377(89)90065-5","volume":"8","author":"K. Malik","year":"1989","unstructured":"Malik, K., Mittal, A.K., Gupta, S.K.: The k most vital arcs in the shortest path problem. Oper. Res. Letters\u00a08, 223\u2013227 (1989)","journal-title":"Oper. Res. Letters"},{"issue":"2","key":"40_CR12","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/S0020-0190(00)00175-7","volume":"79","author":"E. Nardelli","year":"2001","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: A faster computation of the most vital edge of a shortest path. Info. Proc. Letters\u00a079(2), 81\u201385 (2001)","journal-title":"Info. Proc. Letters"},{"issue":"2","key":"40_CR13","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s00453-004-1099-9","volume":"40","author":"E. Nardelli","year":"2004","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: Nearly linear time minimum spanning tree maintenance for transient node failures. Algorithmica\u00a040(2), 119\u2013132 (2004)","journal-title":"Algorithmica"},{"key":"40_CR14","first-page":"166","volume":"35","author":"N. Nisan","year":"2001","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design, Games and Economic. Behaviour\u00a035, 166\u2013196 (2001)","journal-title":"Behaviour"},{"key":"40_CR15","doi-asserted-by":"crossref","unstructured":"Nisan, N., Ronen, A.: Computationally feasible VCG mechanisms. In: Proc. of the 2nd ACM Conf. on Electronic Commerce (EC 2000), pp. 242\u2013252 (2000)","DOI":"10.1145\/352871.352898"},{"key":"40_CR16","unstructured":"Pettie, S., Ramachandran, V.: Computing shortest paths with comparisons and additions. In: Proc. 13th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2002), pp. 267\u2013276 (2002)"},{"key":"40_CR17","first-page":"573","volume":"24","author":"H. Takahashi","year":"1980","unstructured":"Takahashi, H., Matsuyama, A.: An approximate solution for the Steiner problem in graphs. Math. Jap.\u00a024, 573\u2013577 (1980)","journal-title":"Math. Jap."},{"key":"40_CR18","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/0020-0190(82)90137-5","volume":"14","author":"R.E. Tarjan","year":"1982","unstructured":"Tarjan, R.E.: Sensitivity analysis of minimum spanning trees and shortest path problems. Inform. Proc. Lett.\u00a014, 30\u201333 (1982)","journal-title":"Inform. Proc. Lett."},{"key":"40_CR19","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1111\/j.1540-6261.1961.tb02789.x","volume":"16","author":"W. Vickrey","year":"1961","unstructured":"Vickrey, W.: Counterspeculation, auctions and competitive sealed tenders. J. of Finance\u00a016, 8\u201337 (1961)","journal-title":"J. of Finance"},{"key":"40_CR20","doi-asserted-by":"crossref","unstructured":"Wang, W., Li, X.-Y., Wang, Y.: Truthful multicast routing in selfish wireless networks. In: Proc. of the 10th Annual Int. Conf. on Mobile Computing and Networking (INFOCOM 2004), pp. 245\u2013259 (2004)","DOI":"10.1145\/1023720.1023745"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11533719_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T18:36:43Z","timestamp":1586457403000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11533719_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540280613","9783540318064"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/11533719_40","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}