On the complexity of finding well-balanced orientations with upper bounds on the out-degrees

DOI10.1007/S10878-022-00962-YarXiv2202.13759MaRDI QIDQ6392329

Zoltán Szigeti, Florian Hoersch

Publication date: 28 February 2022

Abstract: We show that the problem of deciding whether a given graph $G$ has a well-balanced orientation $vecG$ such that $d_{vecG}^{+}(v)leqell(v)$ for all $vinV(G)$ for a given function $ell:V(G)ightarrowmathbb{Z}_{geq0}$ is NP-complete. We also prove a similar result for best-balanced orientations. This improves a result of Bern' ath, Iwata, Kir' aly, Kir'aly and Szigeti and answers a question of Frank.

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Vertex degrees (05C07)

This page was built for publication: On the complexity of finding well-balanced orientations with upper bounds on the out-degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6392329)