{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T06:24:50Z","timestamp":1648967090278},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,9,14]],"date-time":"2007-09-14T00:00:00Z","timestamp":1189728000000},"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":[[2007,10,15]]},"DOI":"10.1007\/s00453-007-9016-7","type":"journal-article","created":{"date-parts":[[2007,9,13]],"date-time":"2007-09-13T14:03:30Z","timestamp":1189692210000},"page":"171-191","source":"Crossref","is-referenced-by-count":5,"title":["Exact and Approximate Truthful Mechanisms for the Shortest Paths Tree Problem"],"prefix":"10.1007","volume":"49","author":[{"given":"Luciano","family":"Gual\u00e0","sequence":"first","affiliation":[]},{"given":"Guido","family":"Proietti","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,9,14]]},"reference":[{"key":"9016_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\u201901), pp.\u00a0482\u2013491 (2001)","DOI":"10.1109\/SFCS.2001.959924"},{"key":"9016_CR2","doi-asserted-by":"crossref","unstructured":"Buchsbaum, A.L., Kaplan, H., Rogers, A., Westbrook, J.: Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators. In: Proc. 30th ACM Symp. on Theory of Computing (STOC\u201998), pp. 279\u2013288 (1998)","DOI":"10.1145\/276698.276764"},{"issue":"6","key":"9016_CR3","doi-asserted-by":"crossref","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 time complexity. J. ACM 47(6), 1028\u20131047 (2000)","journal-title":"J. ACM"},{"key":"9016_CR4","unstructured":"Cisco Systems Inc. \u00a9 : Internetworking Technologies Handbook. Cisco Press (2004)"},{"key":"9016_CR5","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BF01726210","volume":"8","author":"E. Clarke","year":"1971","unstructured":"Clarke, E.: Multipart pricing of public goods. Public Choice 8, 17\u201333 (1971)","journal-title":"Public Choice"},{"issue":"3","key":"9016_CR6","doi-asserted-by":"crossref","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. ACM 34(3), 596\u2013615 (1987)","journal-title":"J. ACM"},{"key":"9016_CR7","doi-asserted-by":"crossref","unstructured":"Gabow, H.N.: A scaling algorithm for weighted matching on general graphs. In: Proc. 26th IEEE Symp. on Foundations of Computer Science (FOCS\u201985), pp.\u00a090\u2013100 (1985)","DOI":"10.1109\/SFCS.1985.3"},{"issue":"4","key":"9016_CR8","doi-asserted-by":"crossref","first-page":"617","DOI":"10.2307\/1914085","volume":"41","author":"T. Groves","year":"1973","unstructured":"Groves, T.: Incentives in teams. Econometrica 41(4), 617\u2013631 (1973)","journal-title":"Econometrica"},{"key":"9016_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1007\/11533719_40","volume-title":"Proc. 11th Int. Computing and Combinatorics Conference (COCOON\u201905)","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: Proc. 11th Int. Computing and Combinatorics Conference (COCOON\u201905). Lecture Notes in Computer Science, vol.\u00a03595, pp.\u00a0390\u2013400. Springer, New York (2005)"},{"key":"9016_CR10","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\u201901), pp.\u00a0252\u2013259 (2001)","DOI":"10.1109\/SFCS.2001.959899"},{"key":"9016_CR11","doi-asserted-by":"crossref","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. Lett. 8, 223\u2013227 (1989)","journal-title":"Oper. Res. Lett."},{"issue":"2","key":"9016_CR12","doi-asserted-by":"crossref","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. Inf. Process. Lett. 79(2), 81\u201385 (2001)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"9016_CR13","doi-asserted-by":"crossref","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 36(4), 361\u2013374 (2003)","journal-title":"Algorithmica"},{"issue":"1","key":"9016_CR14","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 296(1), 167\u2013177 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"9016_CR15","doi-asserted-by":"crossref","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 40(2), 119\u2013132 (2004)","journal-title":"Algorithmica"},{"key":"9016_CR16","doi-asserted-by":"crossref","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 Econ. Behav. 35, 166\u2013196 (2001)","journal-title":"Games Econ. Behav."},{"key":"9016_CR17","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":"9016_CR18","unstructured":"Pettie, S., Ramachandran, V.: Computing shortest paths with comparisons and additions. In: Proc. 13th ACM Symp. on Discrete Algorithms (SODA\u201902), pp.\u00a0267\u2013276 (2002)"},{"key":"9016_CR19","doi-asserted-by":"crossref","unstructured":"Proietti, G., Widmayer, P.: A truthful mechanism for the non-utilitarian minimum radius spanning tree problem. In: Proc. 17th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA\u201905), pp.\u00a0195\u2013202 (2005)","DOI":"10.1145\/1073970.1073999"},{"issue":"2","key":"9016_CR20","doi-asserted-by":"crossref","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. ACM 22(2), 215\u2013225 (1975)","journal-title":"J. ACM"},{"key":"9016_CR21","doi-asserted-by":"crossref","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. Finance 16, 8\u201337 (1961)","journal-title":"J. Finance"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9016-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9016-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9016-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:44:59Z","timestamp":1559137499000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9016-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,9,14]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,10,15]]}},"alternative-id":["9016"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9016-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,9,14]]}}}