Online Version - Last Updated - 20 Jan 2012 |
 |
| Home |
| |
| Procedures and Resources for Authors |
|
| Information and Resources for Volume Editors |
| |
| Orders and Subscriptions |
| |
| Published Articles |
|
| Upcoming Volumes |
| |
| Contact Us |
| |
| Useful External Links |
| |
| CRPIT Site Search |
Graph Classes and the Complexity of the Graph Orientation Minimizing the Maximum Weighted Outdegree
Asahiro, Y., Miyano, E. and Ono, H.
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)
(local if available)
