Conferences in Research and Practice in Information Technology
  

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
 
    

Upper and Lower Degree Bounded Graph Orientation with Minimum Penalty

Asahiro, Y., Jansson, J., Miyano, E. and Ono, H.

    Given an undirected graph G = (V, E), a graph orientation problem is to decide a direction for each edge so that the resulting directed graph ⃗G = (V, ��(E)) satisfies a certain condition, where ��(E) is a set of assignments of a direction to each edge {u, v} �� E. Among many conceivable types of conditions, we consider a degree constrained orientation: Given positive integers av and bv for each v (av �� bv), decide an orientation of G so that av �� |{(v, u) �� ��(E)}| �� bv holds for every v �� V . However, such an orientation does not always exist. In this case, it is desirable to find an orientation that best fits the condition instead. In this paper, we consider the problem of finding an orientation that minimizes��v��V cv, where cv is a penalty incurred for v��s violating the degree constraint. As penalty functions, several classes of functions can be considered, e.g., linear functions, convex functions and concave functions. We show that the degree-constrained orientation with any convex (including linear) penalty function can be solved in O(m1.5 min{��0.5, log(nC)}), where n = |V|,m = |E|, �� and C are the maximum degree and the largest magnitude of a penalty, respectively. In contrast, it has no polynomial approximation algorithm whose approximation factor is better than 1.3606, for concave penalty functions, unless P=NP; it is APX-hard. This holds even for step functions, which are considered concave. For trees, the problem with any penalty functions can be solved exactly in O(n log ��) time, and if the penalty function is convex, it is solvable in linear time.
Cite as: Asahiro, Y., Jansson, J., Miyano, E. and Ono, H. (2012). Upper and Lower Degree Bounded Graph Orientation with Minimum Penalty. In Proc. Computing: The Australasian Theory Symposium (CATS 2012) Melbourne, Australia. CRPIT, 128. Mestre, J. Eds., ACS. 139-146
pdf (from crpit.com) pdf (local if available) BibTeX EndNote GS