Art

J-GLOBAL ID：201502228954483754   Reference number：15A0192621

次数制約のあるグラフ有向化問題の計算複雑さについて

Author (4)： ASAHIRO YUICHI (九州産大 情報科学) ,  JESUPA JANSON (京大 化研 バイオインフォマティクスセ) ,  MIYANO EIJI (九州工大 大学院情報工学研究院) ,  ONO HIROTAKA (九大 大学院経済学研究院)
Material： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
Volume： 114  Issue： 312(CAS2014 87-104)  Page： 105-112  Publication year： Nov. 13, 2014 
JST Material Number： S0532B  ISSN： 0913-5685  Document type： Proceedings
Article type： 短報  Country of issue： Japan (JPN)  Language： JAPANESE (JA)

Thesaurus term： *directed graph ,  dimensionless number ,  *computational complexity ,  vertex ,  undirected graph ,  degree

JST classification (1)： Basics of graph theory  (IA02020S)

Reference (23)：

• Asahiro, Y., Jansson, J., Miyano, E., and Ono, H.: Upper and lower degree bounded graph orientation with minimum penalty. In Proc. of CATS 2012, CRPIT Series, Vol. 128, 139-146, 2012.
• Asahiro, Y., Jansson, J., Miyano, E., and Ono, H.: Graph orientations optimizing the number of light or heavy vertices. In Proc. of ISCO 2012, LNCS, Vol. 7422, 332-343, 2012.
• 朝廣雄一, ジェスパージャンソン, 宮野英次, 小野廣隆: 次数制約のあるグラフ有向化問題の近似について. 電子情報通信学会コンピュテーション研究会, 信学技報, Vol.113, No.371, COMP2013-58, pp.123-130, 2013 年 12 月.
• Asahiro, Y., Jansson, J., Miyano, E., Ono, H., and Zenmyo, K: Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree. Journal of Combinatorial Optimization 22(1) 78-96, 2011.
• Chlebik, M. and Chlebikova, J.: Complexity of approximating bounded variants of optimization problems. Theor. Comput. Sci. 354(3), 320-338, 2006.

Terms in the title (5)： 次数 ,  制約 ,  グラフ ,  問題 ,  計算複雑さ