Art

J-GLOBAL ID：202002231241911010   Reference number：20A0114520

グラフの2等分割問題に対するアルゴリズムと計算複雑性

Author (3)： KOBAYASHI YASUAKI (京大) ,  SONE TAIGA (京大) ,  HANAKA TESSHU (中央大)
Material： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
Volume： 119  Issue： 314(MSS2019 23-40)  Page： 41-46  Publication year： Nov. 21, 2019 
JST Material Number： S0532B  ISSN： 0913-5685  Document type： Proceedings
Article type： 原著論文  Country of issue： Japan (JPN)  Language： JAPANESE (JA)

Thesaurus term： *graph ,  *division and resolution ,  maximum problem ,  minimum problem ,  NP hard ,  *dynamic programming ,  algorithm ,  weighting ,  computational complexity ,  wooden structure
Semi thesaurus term： computational complexity

JST classification (2)： Basics of graph theory  (IA02020S) ,  Mathematical programmings  (KA03030M)

Reference (18)：

• H. L. Bodlaender, K. Jansen: On the complexity of the maximum cut problem. Nordic Journal of Computing 7(1): 14-31 (2000)
• A. Boyacı, T. Ekim, M. Shalom: A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs. Information Processing Letters 121, 29-33 (2017)
• T. N. Bui, S. Chaudhuri, F. T. Leighton, M. Sipser: Graph bisection algorithms with good average case behavior. Combinatorica 7(2), 171-191 (1987)
• B. Courcelle, S. Olariu: Upper bounds to the clique width of graphs. Discrete Applied Mathematics 101(1-3), 77-144 (2000)
• M. Cygan, P. Komosa, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, S. Saurabh, M. Wahlström: Randomized contractions meet lean decompositions. arXiv:1810.06864 (2018)

Terms in the title (3)： グラフ ,  アルゴリズム ,  計算複雑性