{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:29:11Z","timestamp":1725568151200},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540287001"},{"type":"electronic","value":"9783540319252"}],"license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"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":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11549468_103","type":"book-chapter","created":{"date-parts":[[2010,10,25]],"date-time":"2010-10-25T13:18:34Z","timestamp":1288012714000},"page":"941-951","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Efficient Truthful Mechanisms for the Single-Source Shortest Paths Tree Problem"],"prefix":"10.1007","author":[{"given":"Luciano","family":"Gual\u00e0","sequence":"first","affiliation":[]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"103_CR1","doi-asserted-by":"crossref","unstructured":"Archer, A., Tardos, \u00c9.: Truthful mechanisms for one-parameter agents. In: Proc. 42nd IEEE Symp. on Foundations of Computer Science (FOCS 2001), pp. 482\u2013491 (2001)","DOI":"10.1109\/SFCS.2001.959924"},{"key":"103_CR2","series-title":"Lecture Notes in Computer Science","first-page":"279","volume-title":"Analysis of Dynamical and Cognitive Systems","author":"A.L. Buchsbaum","year":"1995","unstructured":"Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.: Linear-time pointermachine algorithms for least common ancestors, MST verification, and dominators. In: Andersson, S.I. (ed.) Summer University of Southern Stockholm 1993. LNCS, vol.\u00a0888, pp. 279\u2013288. Springer, Heidelberg (1995)"},{"key":"103_CR3","unstructured":"Cisco Systems Inc.\u00a9, Internetworking Technologies Handbook, Cisco Press (2004)"},{"key":"103_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":"3","key":"103_CR5","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1145\/28869.28874","volume":"34","author":"M.L. Fredman","year":"1987","unstructured":"Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. of the ACM\u00a034(3), 596\u2013615 (1987)","journal-title":"J. of the ACM"},{"issue":"4","key":"103_CR6","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":"103_CR7","unstructured":"Gual\u00e0, L., Proietti, G.: Optimal MST sensitivity analysis on a pointer machine, manuscript submitted for publication (2005)"},{"key":"103_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"390","DOI":"10.1007\/11533719_40","volume-title":"Computing and Combinatorics","author":"L. Gual\u00e0","year":"2005","unstructured":"Gual\u00e0, L., Proietti, G.: A truthful (2-2\/k)-approximation mechanism for the Steiner tree problem with k terminals. In: Wang, L. (ed.) COCOON 2005. LNCS, vol.\u00a03595, pp. 390\u2013400. Springer, Heidelberg (2005) (to appear)"},{"key":"103_CR9","doi-asserted-by":"crossref","unstructured":"Hershberger, J., Suri, S.: Vickrey prices and shortest paths: what is an edge worth? In: Proc. 42nd IEEE Symp. on Foundations of Computer Science (FOCS 2001), pp. 252\u2013259 (2001)","DOI":"10.1109\/SFCS.2001.959899"},{"key":"103_CR10","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":"103_CR11","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":"4","key":"103_CR12","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/s00453-003-1024-7","volume":"36","author":"E. Nardelli","year":"2003","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: Swapping a failing edge of a single source shortest paths tree is good and fast. Algorithmica\u00a036(4), 361\u2013374 (2003)","journal-title":"Algorithmica"},{"issue":"1","key":"103_CR13","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0304-3975(02)00438-3","volume":"296","author":"E. Nardelli","year":"2003","unstructured":"Nardelli, E., Proietti, G., Widmayer, P.: Finding the most vital node of a shortest path. Theoretical Computer Science\u00a0296(1), 167\u2013177 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"103_CR14","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":"103_CR15","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1006\/game.1999.0790","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":"Games and Economic Behaviour"},{"key":"103_CR16","volume-title":"A course in Game Theory","author":"M.J. Osborne","year":"1994","unstructured":"Osborne, M.J., Rubinstein, A.: A course in Game Theory. MIT Press, Cambridge (1994)"},{"key":"103_CR17","unstructured":"Pettie, S., Ramachandran, V.: Computing shortest paths with comparisons and additions. In: Proc. 13th ACM Symp. on Discrete Algorithms (SODA 2002), pp. 267\u2013276 (2002)"},{"issue":"1","key":"103_CR18","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/505241.505243","volume":"49","author":"S. Pettie","year":"2002","unstructured":"Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. of the ACM\u00a049(1), 16\u201334 (2002)","journal-title":"J. of the ACM"},{"key":"103_CR19","doi-asserted-by":"crossref","unstructured":"Proietti, G., Widmayer, P.: A truthful mechanism for the non-utilitarian minimum radius spanning tree problem. In: 17th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA 2005) (2005) (to appear)","DOI":"10.1145\/1073970.1073999"},{"issue":"2","key":"103_CR20","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","volume":"22","author":"R.E. Tarjan","year":"1975","unstructured":"Tarjan, R.E.: Efficiency of a good but not linear set union algorithm. J. of the ACM\u00a022(2), 215\u2013225 (1975)","journal-title":"J. of the ACM"},{"key":"103_CR21","doi-asserted-by":"publisher","first-page":"8","DOI":"10.2307\/2977633","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"}],"container-title":["Lecture Notes in Computer Science","Euro-Par 2005 Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11549468_103","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,19]],"date-time":"2020-04-19T20:11:34Z","timestamp":1587327094000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11549468_103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540287001","9783540319252"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11549468_103","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]},"assertion":[{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}