New answers tagged

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