Name
Abstract | ||
|---|---|---|
Given a graph G = (V, E), we say that a vertex subset S ⊆ V covers a vertex v ∈ V if the edge-connectivity between S and v is at least a given integer k, and also say that S covers an edge vw ∈ E if v and w are covered. We propose the multi-commodity source location problem, which is such that given a vertex- and edge-weighted graph G, r players each select p vertices, and obtain a profit that is the total weight of covered vertices and edges. However, vertices selected by one player cannot be selected by the other players. The goal is to maximize the total profits of all players. We show that the price of greed, which indicates the ratio of the total profit of cooperating players to that of selfish players, is tightly bounded by min{r, p}. Also when k = 2, we obtain tight bounds for vertex-unweighted trees. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-540-77891-2_16 | WALCOM'08 Proceedings of the 2nd international conference on Algorithms and computation |
Keywords | Field | DocType |
total profit,covered vertex,select p vertex,total weight,vertex subset,vertex v,edge-weighted graph,graph G,integer k,edge vw,Multi-commodity source location problem | Integer,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Bound graph,Vertex (graph theory),Commodity,Neighbourhood (graph theory),Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
13 | 1 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-77890-X | 0 | 0.34 |
References | Authors | |
11 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hiro Ito | 1 | 290 | 39.95 |
| Mike Paterson | 2 | 744 | 152.22 |
| Kenya Sugihara | 3 | 9 | 3.00 |