Graph orientations optimizing the number of light or heavy vertices

Yuichi Asahiro, Jesper Jansson, Eiji Miyano, Hirotaka Ono

研究成果: ジャーナルへの寄稿学術誌査読

7 被引用数 (Scopus)


This paper introduces four graph orientation problems named MAXIMIZE W-LIGHT, MINIMIZE W-LIGHT, MAXIMIZE W-HEAVY, and MINIMIZE W-HEAVY, where W can be any fixed non-negative integer. In each problem, the input is an undirected, unweighted graph G and the objective is to assign a direction to every edge in G so that the number of vertices with outdegree at most W or at least W in the resulting directed graph is maximized or minimized. A number of results on the computational complexity and polynomial-time approximability of these problems for different values of W and various special classes of graphs are derived. In particular, it is shown that MAXIMIZE 0-LIGHT and MINIMIZE 1-HEAVY are identical to MAXIMUM INDEPENDENT SET and MINIMUM VERTEX COVER, respectively, so by allowing the value of W to vary, we obtain a new generalization of the two latter problems.

ジャーナルJournal of Graph Algorithms and Applications
出版ステータス出版済み - 8月 1 2015

!!!All Science Journal Classification (ASJC) codes

  • 理論的コンピュータサイエンス
  • コンピュータサイエンス一般
  • コンピュータ サイエンスの応用
  • 幾何学とトポロジー
  • 計算理論と計算数学


「Graph orientations optimizing the number of light or heavy vertices」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。