Given an undirected graph with edge weights, we are
asked to find an orientation, i.e., 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 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 tight thresholds of complexity:
We show that MMO is (i) in P for cactuses, (ii)
weakly NP-hard for outerplanar graphs, and also (iii)
strongly NP-hard for P4-bipartite graphs. The latter
two are minimal superclasses of the former. Also, we
show the NP-hardness for the other related graph
classes, diamond-free, house-free, series-parallel, bipartite
and planar. |
| Cite as: Asahiro, Y., Miyano, E. and Ono, H. (2008). Graph Classes and the Complexity of the Graph Orientation Minimizing the Maximum Weighted Outdegree. In Proc. Fourteenth Computing: The Australasian Theory Symposium (CATS 2008), Wollongong, NSW, Australia. CRPIT, 77. Harland, J. and Manyem, P., Eds. ACS. 97-106. |
(from crpit.com)
