Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree
复制标题
图类和图方向的复杂性最小化最大加权出度
DOI：
10.1016/j.dam.2010.11.003
复制
发表时间：
2011
影响因子：
1.1
通讯作者：
Hirotaka Ono
中科院分区：
文献类型：
--
作者：
Yuichi Asahiro;Eiji Miyano;Hirotaka Ono
给定一个带边权的无向图，我们被要求找到一个方向，即为每条边分配一个方向，以便最小化所得到的有向图中的加权最大出度。这个问题被称为MMO，是著名的最小完工时间问题的一个限制性变体。在以前的研究中，它表明，MMO是在P的树，弱NP-困难的平面二部图，和强NP-困难的一般图。这些图形类之间仍然存在差距。本文的目的是显示更严格的阈值的复杂性：我们表明，MMO是（i）在P仙人掌图，（ii）弱NP-硬的外平面图，以及（iii）强NP-硬的图，这是平面和二部。这意味着P4-二部图、无钻石图或无房子图的NP-硬度，其中每一个图都是仙人掌的超类。我们还证明了（iv）串-平行图和多外平面图的NP-困难性，以及（v）对树宽有界的图给出了一个伪多项式时间算法。
Given an undirected graph with edge weights, we are asked to find an orientation, that is, an assignment of a direction to each edge, so as to minimize the weighted maximum outdegree in the resulted directed graph. The problem is called MMO, and is a restricted variant of the well-known minimum makespan problem. As in previous studies, it is shown that MMO is in P for trees, weak NP-hard for planar bipartite graphs, and strong NP-hard for general graphs. There are still gaps between those graph classes. The objective of this paper is to show tighter thresholds of complexity: We show that MMO is (i) in P for cactus graphs, (ii) weakly NP-hard for outerplanar graphs, and also (iii) strongly NP-hard for graphs which are both planar and bipartite. This implies the NP-hardness for P4-bipartite, diamond-free or house-free graphs, each of which is a superclass of cactus. We also show (iv) the NP-hardness for series–parallel graphs and multi-outerplanar graphs, and (v) present a pseudo-polynomial time algorithm for graphs with bounded treewidth.