Art

J-GLOBAL ID：202002290037508673   Reference number：20A0896324

Efficient enumeration of minimal multiway cuts

最小限のマルチウェイカットの効率的な列挙

Author (2)： KURITA Kazuhiro (Hokkaido Univ.) ,  KOBAYASHI Yasuaki (Kyoto Univ.)
Material： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
Volume： 2020  Issue： AL-177  Page： Vol.2020-AL-177,No.6,1-5 (WEB ONLY)  Publication year： Mar. 09, 2020 
JST Material Number： U0451A  Document type： Proceedings
Article type： 原著論文  Country of issue： Japan (JPN)  Language： ENGLISH (EN)

Thesaurus term： *undirected graph ,  NP hard ,  *algorithm ,  learning ,  approximation method ,  problem solving ,  graph theory
Semi thesaurus term： semi-supervised learning ,  *マルチウェイカット ,  approximate algorithm

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

Reference (21)：

• Arora, S., Karger, D. and Karpinski, M.: Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems, Journal of Computer and System Sciences, Vol. 58, No. 1, pp. 193-210 (online), DOI: https://doi.org/10.1006/jcss.1998.1605 (1999).
• Avis, D. and Fukuda, K.: Reverse search for enumeration, Discrete Applied Mathematics, Vol. 65, No. 1, pp. 21-46 (online), DOI: https://doi.org/10.1016/0166-218X(95)00026-N (1996).
• Bateni, M., Hajiaghayi, M., Klein, P. N. and Mathieu, C.: A Polynomial-Time Approximation Scheme for Planar Multiway Cut, Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, USA, Society for Industrial and Applied Mathematics, p. 639-655 (2012).
• Chen, D. Z. and Wu, X.: Efficient Algorithms for k-Terminal Cuts on Planar Graphs, Algorithmica, Vol. 38, No. 2, pp. 299-316 (online), DOI: 10.1007/s00453-003-1061-2 (2004).
• Călinescu, G., Karloff, H. and Rabani, Y.: An Improved Approximation Algorithm for MULTIWAY CUT, Journal of Computer and System Sciences, Vol. 60, No. 3, pp. 564-574 (online), DOI: https://doi.org/10.1006/jcss.1999.1687 (2000).