Name
Abstract | ||
|---|---|---|
The reachability r(D) of a directed graph D is the number of ordered pairs of distinct vertices (x,y) with a directed path from x to y. Consider a game associated with a graph G=(V,E) involving two players (maximizer and minimizer) who alternately select edges and orient them. The maximizer attempts to maximize the reachability, while the minimizer attempts to minimize the reachability, of the resulting digraph. If both players play optimally, then the reachability is fixed. Parameters that assign a value to each graph in this manner are called competitive parameters. We determine the competitive-reachability for special classes of graphs and discuss which graphs achieve the minimum and maximum possible values of competitive-reachability. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.disc.2006.01.020 | Discrete Mathematics |
Keywords | Field | DocType |
reachability,competitive parameters,orientations,directed graph | Discrete mathematics,Combinatorics,Line graph,Path (graph theory),Transitive reduction,Directed graph,Cycle graph,Implicit graph,Null graph,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
306 | 6 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Suk Jai Seo | 1 | 4 | 2.59 |
| Peter J. Slater | 2 | 593 | 132.02 |