Presentation	2011-12-16 Minimizing Penalty on Upper and Lower Degree Constrained Graph Orientation Yuichi ASAHIRO, Jesper JANSSON, Eiji MIYANO, Hirotaka ONO,
PDF Download Page	PDF download Page Link
Abstract(in Japanese)	(See Japanese page)
Abstract(in English)	Given an undirected graph G = (V, E), a graph orientation problem is to decide a direction of each edge so that the resulting directed graph G^^→ = (V, Λ(E)) satisfies a certain condition, where Λ(E) is a set of an assignment of a direction to each edge {u,v} ∈ E. We consider a degree constrained orientation: Given positive integers a_v and b_v for each v (a_v ≦ b_v), decide an orientation of G so that a_v ≦ |{(v,u) ∈ Λ(E)}| ≦ b_v holds for as many vertices v's as possible. In this paper, we consider the problem of finding an orientation that minimizes Σ_c_v, where c_v is a penalty incurred for v's violating the degree constraint. We show that: (i) The degree-constrained orientation with any convex (including linear) penalty function can be solved in O(m^<1.5>min{log(nC), Δ^<0.5>}), where n = |V|,m = |E|, Δ and C are the maximum degree and the largest magnitude of a penalty, respectively. (ii) In contrast, it is APX-hard for step (i.e., concave) penalty functions. (iii) For trees, the problem with any penalty functions can be solved in O(n log Δ) time, and if the penalty function is convex, it is solvable in linear time.
Keyword(in Japanese)	(See Japanese page)
Keyword(in English)
Paper #	COMP2011-41
Date of Issue

Conference Information
Committee	COMP
Conference Date	2011/12/9(1days)
Place (in Japanese)	(See Japanese page)
Place (in English)
Topics (in Japanese)	(See Japanese page)
Topics (in English)
Chair
Vice Chair
Secretary
Assistant

Paper Information
Registration To	Theoretical Foundations of Computing (COMP)
Language	ENG
Title (in Japanese)	(See Japanese page)
Sub Title (in Japanese)	(See Japanese page)
Title (in English)	Minimizing Penalty on Upper and Lower Degree Constrained Graph Orientation
Sub Title (in English)
Keyword(1)
1st Author's Name	Yuichi ASAHIRO
1st Author's Affiliation	Department of Information Science, Kyushu Sangyo University()
2nd Author's Name	Jesper JANSSON
2nd Author's Affiliation	Ochanomizu University
3rd Author's Name	Eiji MIYANO
3rd Author's Affiliation	Department of Systems Design and Informatics, Kyushu Institute of Technology
4th Author's Name	Hirotaka ONO
4th Author's Affiliation	Department of Economic Engineering, Kyushu University
Date	2011-12-16
Paper #	COMP2011-41
Volume (vol)	vol.111
Number (no)	360
Page	pp.pp.-
#Pages	8
Date of Issue