New answers tagged dag
2
For a DAG, a simple linear-time algorithm is all that is needed.
First, prune all vertices not reachable either from $s$ or to $t$.
Let $G' = (V', E')$ be the pruned graph.
Then, compute any topological ordering $\pi$ of $G'$.
Let $(u, v) \in E'$ be an edge. I assert the edge $(u, v)$ is a bottleneck if and only if $\pi(u) + 1 = \pi(v)$ and there doesn't ...
3
Compute the dominator tree of the flow graph $(G,s)$, i.e., the graph $G$ with source node $s$. Let $s=v_0,v_1,\dots,v_{k-1},v_k=t$ be the sequence of nodes in the path from $s$ to $t$ in the dominator tree. Check each pair $(v_i,v_{i+1})$ of consecutive nodes in this sequence; if it is an edge of $G$, it is visited on every $s,t$-path, so output it. It ...
0
Here's an implementation of D.W.'s algorithm (the $O(n^2)$ version) in C++. There was some subtlety around the base case of the recurrence; A needs to be indexed on std::optional<NodeId>, where A[std::nullopt] = 0 is the base case.
2
I suggest using dynamic programming. Because your graph forms a path, we can use dynamic programming (considering all prefixes of the path), solving once for each candidate for the maximum total weight of the parts. Details below.
Let $S$ denote the sum of the weights of the cut edges (i.e., the first part of your objective function) and $M$ the maximum ...
Top 50 recent answers are included
