New answers tagged

2

You can solve this in $O(|V| \cdot |E|)$ time. Construct a digraph with vertices of the form $\langle v,b\rangle$ where $v \in V$, $b \in \{0,1\}$, as follows: for each edge $v \stackrel{t}{\to} w$ in your graph, add the edges $\langle v,b \rangle \to \langle w,b + t \bmod 2 \rangle$ for each $b \in \{0,1\}$ to the new graph. Then, for each $v \in V$, ...


2

Construct the edge-vertex incidence matrix: rows correspond to edges, columns to vertices, and there is a $1$ if the edge is incident to the vertex. Add another columns full of $1$'s. You want to know whether there is a subset of the rows summing to the vector $0,\ldots,0,1$ (modulo 2). You can find out using Gaussian elimination, in polynomial time. What ...


0

Let us say that an edge $e$ in $G$ is BAD if there exists a cycle in $G$ in which $e$ has maximum weight. Define ${\cal B}=\{e~|~e$ is BAD in $G\}$ to be the collection of all bad edges. Your question is whether the graph $(G - {\cal B})$ the MST of $G$ (assuming all edge-weights are distinct). The answer is YES! In order to prove this it suffices to ...


0

Sorry if I didn't understand your question, but what I think you meant to ask is, whether it is possible for an edge to not be in a MST if this edge is not in a cycle. Here's my answer. Let us assume that we have an edge (u,v) in a graph G, that isn't part of a cycle. This would mean that there is no path from u to v that isn't the edge (u,v). If the edge (...


1

On the question from title For fixed sink $s \in S$ you can find maximal distance from each vertex to this sink by running dynamic programming on topological order: $$ d(v)= \begin{cases} 0\text{ if } v = s\\ -\infty \text{ if } v \not= s \land v \in S\\ 1 + max_{(v, u) \in E} d(u) \end{cases} $$ You can run this algorithm for every $s \in S$ to get the ...


0

It's possible to use BK-Trees to speed this up. Inserting $n$ elements into the tree takes $O(n \log n)$ time. After this you can query the tree for all strings whose edit distance is exactly one away from your input. Doing this for all strings again takes $O(n^2)$ complexity, however with a very small constant factor (this page mentions only 5-8% of the ...


0

Many such problems can be solved by modifying the input instance rather than a known algorithm. In your case you can consider your graph as directed and create a new directed graph $G'$ the is split into $2$ "layers", $A$, and $B$. Layer $A$ contains a copy of all the vertices in $V$, layer $B$ contains a copy of all the vertices in $V \setminus X$. Given ...


1

for i in V: weight(i) = 0 for e=(i,j) in E: weight(i) = weight(i) + weight(e) weight(j) = weight(j) + weight(e)


0

I am assuming here that you want to calculate the all-pairs shortest paths for a graph using Dijkstra's. First, to find the shortest path between all pairs of vertices, you can create a $ |V|^2 $ matrix where row and column i and j corresponds to the shortest distance from vertex i to vertex j. Second, to mark the all-path shortest paths' path, you simply ...


Top 50 recent answers are included