Graph classes and the complexity of the graph orientation minimizing the maximum weighted outdegree

详细信息    查看全文

• 作者：Yuichi Asahiro^a ; ^{asahiro@is.kyusan-u.ac.jp} ; Eiji Miyano^b ; ^{miyano@ces.kyutech.ac.jp} ; Hirotaka Ono^c ; ^{hirotaka@en.kyushu-u.ac.jp}
• 关键词：Graph orientation ; Min– ; max optimization ; 10003756&_rdoc=3&_issn=0166218X&_acct=C0000
• 刊名：Discrete Applied Mathematics
• 出版年：2011
• 出版时间：6 April 2011
• 年：2011
• 卷：159
• 期：7
• 页码：498-508
• 全文大小：729 K

文摘

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 for trees, weak -hard for planar bipartite graphs, and strong -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 for cactus graphs, (ii) weakly -hard for outerplanar graphs, and also (iii) strongly -hard for graphs which are both planar and bipartite. This implies the -hardness for P₄-bipartite, diamond-free or house-free graphs, each of which is a superclass of cactus. We also show (iv) the -hardness for series–parallel graphs and multi-outerplanar graphs, and (v) present a pseudo-polynomial time algorithm for graphs with bounded treewidth.