New answers tagged graph-traversal
0
Yes, it is true that there exist two edge-disjoint paths between any two vertices in a connected bridgeless graph.
Define a closed trail as a trail whose last vertex is its first vertex. Note, a trail contains two edge-disjoint paths between any two of its vertices.
Trail combining lemma. Let $G$ be a graph. Suppose a closed trail passes vertex $v$. ...
1
I believe that computing graph dominators will solve your problem. This can be done in $O(|E|\log |V|)$ time (or even faster, though they describe the faster algorithm as "sophisticated") using a 1979 algorithm by Lengauer and Tarjan, which is (at least currently) described here (21 pages -- I have only read the first few pages myself).
Add a new "start" ...
1
I've got bad news. There's no hope for an algorithm whose worst-case running time is polynomial in the size of the weighted graph (unless P = NP, which seems unlikely).
Your problem is as hard as the knapsack problem, which has no polynomial-time algorithm (unless P = NP) when the input is represented in binary. The knapsack problem has a pseudopolynomial ...
1
I ended up using the UCT (MCTS with UCB1) algorithm but with a twist.
Normally, in UCT, the simulation phase is a simulated play-through of a game with moves chosen at random. If the simulated game ends in a win, the node's score, from where the simulation was played out, and all it's parents' scores all the way back to the root, are incremented by 1.
In ...
2
This is the longest path problem. It's NP-hard to find the longest path in a general graph. You can try applying any standard algorithm for finding longest paths. Search on this site for "longest path" and "Hamiltonian path" to find many references. Since you're willing to accept suboptimal solutions, you might look for a heuristic or approximation ...
0
It works because-
For any randomly chosen vertex $u$, the farthest vertex from it lies on one end of the diameter.
If vertex $a$ is one end of the diameter, the farthest vertex from it is the other end.
The first BFS takes you to one end of the diameter and the second BFS from that end takes you to the other end.
Proof
#2 is easy to see why it's true. ...
0
Using the same logic as the recursive algorithm, I added on the stack a pos value which keeps track of the position of the last descendant currently processing.
This was necessary for the "backtrack" steps of the algorithm.
from typing import List
UNDISCOVERED = -1
DISCOVERED = 0
PROCESSED = 1
def is_acyclic(graph: List[list], vertex_count: int) -> ...
4
Hint: find a topological ordering, and for each vertex $v$, in the topological ordering, compute (the score of) the path with the highest score that ends at $v$.
2
Let $A$ be the set of available vertices (including $L$) and let $A(v)$ be the set of available vertices reachable by $v$ with a single move.
Let $M[v,\ell]$ be the number of walks of length exactly $\ell \ge 0$ from vertex $v \in A$.
You have that:
$M[v,0] = 1 \quad \forall v \in A$;
$M[v,\ell] = \sum_{u \in A(v)} M[u,\ell-1] \quad \forall v \in A, \...
0
Let's construct a new graph $G'$.
Every vertex $u$ from $G$ will become a pair of vertexes in $G'$, namely $u_{blue}$ and $u_{green}$ (index stands for the color of incoming edge).
Edge $u_{c_1}\rightarrow w_{c_2}$ in $G'$ exists iff
There is an edge $u \rightarrow w$ in $G$ colored $c_2$
$c_1 \ne c_2$
Now it's easy to see that every path in $G'$ ...
0
After a bit of reading through literature I've come upon "closeness centrality" which is the reciprocal of what I'm calculating (mean distance, which they call "farness" in the article). But I still haven't found any algorithms for finding the "closeness center" (node with maximum closeness centrality) that is faster than $O(N^2)$.
As a heuristic, I have ...
Top 50 recent answers are included
