Huan Zhou

Arc-Weighted Acyclic Orientation of Graphs

Let $D$ be a digraph, and let $w: E(D) \to \{1,2,\ldots \}$ be a positive integer weight assignment on the arcs of $D$. An arc $e=(u,v)$ is called dominating if $w(e) > d_{(D,w)}^+(v)$, where $d_{(D,w)}^+(v)$ denotes the weighted out-degree of $v$. We say $(D,w)$ is acyclic if every non-empty sub-digraph $(D', w)$ has...