Exact and approximate truthful mechanisms for the shortest paths tree problem
From MaRDI portal
Publication:2461546
DOI10.1007/s00453-007-9016-7zbMath1131.68073MaRDI QIDQ2461546
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
Algorithmic mechanism design; Selfish agents; Single-source shortest paths tree; Truthful mechanisms
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