Computer Science – Computer Science and Game Theory
Scientific paper
2009-09-17
Computer Science
Computer Science and Game Theory
v2: Referees' comments incorporated, section on bounded-treewidth graphs expanded
Scientific paper
The Stackelberg Minimum Spanning Tree Game is a two-level combinatorial pricing problem played on a graph representing a network. Its edges are colored either red or blue, and the red edges have a given fixed cost, representing the competitor's prices. The first player chooses an assignment of prices to the blue edges, and the second player then buys the cheapest spanning tree, using any combination of red and blue edges. The goal of the first player is to maximize the total price of purchased blue edges. We study this problem in the cases of planar and bounded-treewidth graphs. We show that the problem is NP-hard on planar graphs but can be solved in polynomial time on graphs of bounded treewidth.
Cardinal Jean
Demaine Erik D.
Fiorini Samuel
Joret Gwenaël
Newman Ilan
No associations
LandOfFree
The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Stackelberg Minimum Spanning Tree Game on Planar and Bounded-Treewidth Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-391048