CS535 Homework 1
计算机Homework代考 Consider a digraph D = (V; A; `) with arbitrary edge-length function `. Let be mean length of a minimum-mean circuit in D.
Due: 6pm, Sep. 8, 2022. 计算机Homework代考
General notations: For a digraph D = (V; A), m := jAj and n := jV j. For an edge-weighted digraph D = (V; A; ), is the edge-length function.
- Consider a digraph D = (V; A) with two distinct vertices s and t. Give an algorithm to Önd an inclusion-wise maximal (not necessarily maximum) edge-disjoint shortest s-t paths in D in O (m + n) time. 计算机Homework代考
- Consider a digraph D = (V; A; `) with arbitrary edge-length function `. Let be mean length of a minimum-mean circuit in D. Give an O (mn)-time algorithm to Önd a vertex-price function p on V such that the p-adjusted edge-length function `p satisÖes that for each a 2 A, `p (a) ; for each a in a minimum-mean circuit, `p (a) = .
- Let D = (V; A) be a digraph, and s and t be two distinct nodes in V . Show that D has no s-t path if and only if there exists a nonnegative integer-valued labeling p of the nodes satisfying that
p (s) = n and p (t) = 0; 计算机Homework代考
for each (u; v) 2 A, p (u)
发表回复
要发表评论，您必须先登录。