All Questions
Tagged with gt.game-theory graph-theory
5 questions
-1
votes
1
answer
134
views
Algorithm for finding traffic equilibrium
I watched a youtube video about a certain interesting property of springs and road networks. It made me think: if we represent a network of roads as a graph where edges are roads described by a ...
6
votes
1
answer
204
views
On bandwidth of graphs
I am trying to find references on algorithms for graphs of bounded bandwidth, in the same way as it is done with treewidth for instance.
I could only find research related to computing the bandwidth, ...
11
votes
2
answers
1k
views
For which families of graphs is Generalized Geography in $P$?
As @Marzio mentioned, the following game is known as Generalized Geography.
Given a graph $G=(V,E)$ and a starting vertex $v \in V$, the game is defined as follows:
At each turn (two players ...
3
votes
0
answers
297
views
Graph connectivity related game [closed]
I was considering the following game on an undirected unweighted graph $G=(V,E)$ (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of ...
10
votes
3
answers
404
views
Refinements of pair approximation for network analysis
When considering interactions on networks, it is usually very hard to calculate the dynamics analytically, and approximations are employed. Mean-field approximations usually end up ignoring the ...