Skip to main content

All Questions

Filter by
Sorted by
Tagged with
-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 ...
Ace shinigami's user avatar
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, ...
Denis's user avatar
  • 9,018
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 ...
R B's user avatar
  • 9,508
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 ...
Dmytro Korduban's user avatar
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 ...
Artem Kaznatcheev's user avatar