New answers tagged graph-traversal
0
Regarding the problem of visiting as many vertices/edges as possible without using any edge twice: one can look at this problem as the problem of finding an Eulerian subgraph with a maximum number of vertices/edges. Or alternatively, as the problem of deleting a minimum number of vertices/edges so as to make a graph Eulerian.
You might be interested in the ...
3
Use a product construction, to construct a new graph whose vertices are given $(x,y,z,k)$, where $k$ counts the index into the sequence of colors (i.e., we are currently at $k$th vertex in that sequence). Then, find the shortest path in this new graph using any standard shortest-path algorithm. If all weights are non-negative, you can use Dijkstra's ...
2
If you are allowed to visit vertices more than once, many graph theorists use the term walk instead of path, i.e., a path is a walk where each vertex is visited only once (others use the pair path and simple path for walk and path).
The shortest walk visiting every vertex may be called a Hamiltonian walk (see MathWorld), although this notion is not nearly as ...
1
Create a graph from the airport coordinates where edges have the haversine distance as weights. Since the graph is a metric graph, you can apply Christofides algorithm. This algorithm is a $\frac 3 2$-appoximation, which means that it gives a solution which is not worse than 50% longer than the optimal.
However, since you want to also minimize the number ...
0
I have looked up a little bit about Thorup's algorithm (see here), but it turns out that:
For simplicity, we assume […] that the input and output size is $O(m)$
Here, $m$ is the number of edges $|E|$. This assumption in fact proves that a hypothesis for the proof is $|V| = O(|E|)$ (since $V$ is part of the input).
That means that even Thorup's ...
1
To the extent of my knowledge, applying BFS on a graph (directed or undirected), starting from the "source" node and visiting only nodes that we can reach using the BFS (that is, we don't run BFS from every node if we didn't see that node already. Only one instance starting from the source node is enough), would require $O(E)$ time.
It follows ...
2
You probably haven't found anything in your searches because this problem is fairly easy to solve, without needing any fancy methods.
If the graph is strongly connected, then it is easy. Let $s$ be the starting node. Pick any vertex $v$ you haven't visited yet, and append a path $s \leadsto v$ followed by some path $v \leadsto s$ (both must exist, since ...
2
No. There has to be a way to verify that your choices led to a correct choice, in polynomial time (with an ordinary deterministic computer). Given a particular Hamiltonian path, there's no way to verify it is the least Hamiltonian path (in polynomial time).
The "space alien" stuff is just intuition, but if you want to know what it means in a ...
0
I believe your problem has been resolved as this is an old question, but here is a solution just to add up to your knowledge.
Proof of Correctness of BFS
First, two kinds of annoying lemmas. These help us formalize what’s going on as the algorithm is running.
Lemma 1. At end of BFS, for all $v ∈ V$, $\newcommand{\dist}{\operatorname{dist}}\dist(v)$ is at ...
1
Note that counting the number of (non empty) paths starting from edge $(q_1, q_2)$ is the same as counting the number of (possibly empty) paths starting from vertex $q_2$. That way, the answer can be given as an array of size $|V|$ for a graph $G = (V, E)$ instead of a matrix of size $|V| \times |V|$.
Knowing that fact, here is an algorithm to compute this ...
Top 50 recent answers are included
