Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation
Degree-Constrained Graph Orientation: Maximum Satisfaction and Minimum Violation
复制标题
度约束图方向：最大满意度和最小违规
DOI：
10.1007/s00224-014-9565-5
复制
发表时间：
2016
影响因子：
0.5
通讯作者：
and Hirotaka Ono
中科院分区：
文献类型：
--
作者：
Yuichi Asahiro;Jesper Jansson;Eiji Miyano;and Hirotaka Ono
无向图G的度约束图定向是将方向分配给图G中的每条边，使得得到的有向图中每个顶点的出度满足指定的下界和/或上界。这样的图定向已经被研究了很长时间，并且知道它们存在的各种特征。在本文中，我们考虑了参考文献(Asahiro et al.LNCS7422,332-343(2012))：对于任何固定的非负整数W，问题MAXW-Light、MINW-Light、Maxw-Heavy和MINW-Heavy以无向图G作为输入，并要求G的方向使最大或最小出度至少为W的顶点的数目最大化或最小化。如Asahiro等人所示。LNCS7422,332-343(2012))。
Adegree-constrained graph orientationof an undirected graphGis an assignment of a direction to each edge inGsuch that the outdegree of every vertex in the resulting directed graph satisfies a specified lower and/or upper bound. Such graph orientations have been studied for a long time and various characterizations of their existence are known. In this paper, we consider four related optimization problems introduced in reference (Asahiro et al. LNCS7422, 332–343 (2012)): For any fixed non-negative integerW, the problemsMAXW-LIGHT,MINW-LIGHT,MAXW-HEAVY, andMINW-HEAVYtake as input an undirected graphGand ask for an orientation ofGthat maximizes or minimizes the number of vertices with outdegree at mostWor at leastW. As shown in Asahiro et al. LNCS7422, 332–343 (2012)).