# Stackelberg Shortest Path Tree Game, Revisited

Preprint · Sergio Cabello

- Archive id: arxiv:1207.2317
- Published: 2012-07-10
- arXiv: https://arxiv.org/abs/1207.2317
- Source URL: https://arxiv.org/abs/1207.2317
- PDF: https://arxiv.org/pdf/1207.2317
- Provenance: arxiv

## Abstract

Let $G(V,E)$ be a directed graph with $n$ vertices and $m$ edges. The edges $E$ of $G$ are divided into two types: $E\_F$ and $E\_P$. Each edge of $E\_F$ has a fixed price. The edges of $E\_P$ are the priceable edges and their price is not fixed a priori. Let $r$ be a vertex of $G$. For an assignment of prices to the edges of $E\_P$, the revenue is given by the following procedure: select a shortest path tree $T$ from $r$ with respect to the prices (a tree of cheapest paths); the revenue is the sum, over all priceable edges $e$, of the product of the price of $e$ and the number of vertices below $e$ in $T$. Assuming that $k=\|E\_P\|\\ge 2$ is a constant, we provide a data structure whose construction takes $O(m+n\\log^{k-1} n)$ time and with the property that, when we assign prices to the edges of $E\_P$, the revenue can be computed in $(\\log^{k-1} n)$. Using our data structure, we save almost a linear factor when computing the optimal strategy in the Stackelberg shortest paths tree game of \[D. Bil{ò} and L. Gual{à} and G. Proietti and P. Widmayer. Computational aspects of a 2-Player Stackelberg shortest paths tree game. Proc. WINE 2008\].

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.