Exact and approximate truthful mechanisms for the shortest paths tree problem

DOI10.1007/s00453-007-9016-7zbMath1131.68073MaRDI QIDQ2461546

Guido Proietti, Luciano Gualà

Publication date: 28 November 2007

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9016-7

zbMATH Keywords

Algorithmic mechanism design; Selfish agents; Single-source shortest paths tree; Truthful mechanisms

Mathematics Subject Classification ID

90B18: Communication networks in operations research

68M10: Network design and communication in computer systems

68R10: Graph theory (including graph drawing) in computer science

Related Items

A faster computation of all the best swap edges of a shortest paths tree, New bounds for truthful scheduling on two unrelated selfish machines, Path-Fault-Tolerant Approximate Shortest-Path Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The k most vital arcs in the shortest path problem
• Finding the most vital node of a shortest path.
• Polynomial time algorithms for 2-edge-connectivity augmentation problems
• A faster computation of the most vital edge of a shortest path
• Nearly linear time minimum spanning tree maintenance for transient node failures
• Efficiency of a Good But Not Linear Set Union Algorithm
• Incentives in Teams
• A minimum spanning tree algorithm with inverse-Ackermann type complexity
• Computing and Combinatorics
• Algorithmic mechanism design