论文标题
关于找到均衡的方向的复杂性，远距离上的上限
On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
论文作者
论文摘要
我们表明，确定给定的图$ g $是否具有均衡的方向$ \ vec {g} $，以使给定函数$ \ ell：ell e \ ell e e \ ell： 0} $是np complete。我们还证明了最佳平衡方向的类似结果。这改善了Bern \'Ath，Iwata，Kir \'Aly，Király和Szigeti的结果，并回答了弗兰克的问题。
We show that the problem of deciding whether a given graph $G$ has a well-balanced orientation $\vec{G}$ such that $d_{\vec{G}}^+(v)\leq \ell(v)$ for all $v \in V(G)$ for a given function $\ell:V(G)\rightarrow \mathbb{Z}_{\geq 0}$ is NP-complete. We also prove a similar result for best-balanced orientations. This improves a result of Bern\' ath, Iwata, Kir\' aly, Király and Szigeti and answers a question of Frank.
