文献

J-GLOBAL ID：202002226982178267   整理番号：20A2612564

最小Steiner問題に関する多項式遅延エミュレーション

Polynomial Delay Enumeration for Minimal Steiner Problems

著者 (3件)： KOBAYASHI Yasuaki (Kyoto Univ., Kyoto, JPN) ,  KURITA Kazuhiro (National Inst. of Informatics, Tokyo, JPN) ,  WASA Kunihiro (Toyohashi Univ. Technol., Aichi, JPN)
資料名： 電子情報通信学会技術研究報告(Web)  (IEICE Technical Report (Web))
巻： 120  号： 209(COMP2020 11-17)  ページ： 39-46 (WEB ONLY)  発行年： 2020年10月16日 
JST資料番号： U2030A  ISSN： 2432-6380  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

シソーラス用語： *Steiner木 ,  *計算理論 ,  時間 ,  遅れ ,  エミュレーション ,  無向グラフ ,  スパンニング木 ,  NP困難 ,  *アルゴリズム ,  グラフ ,  グラフアルゴリズム
準シソーラス用語： 多項式時間 ,  遅延 ,  最小木 ,  全域木

分類 (1件)： 計算理論  (JB02000A)

引用文献 (28件)：

• S. Beyer and M. Chimani. Strong steiner tree approximations in practice. ACM J. Exp. Algorithmics,24(1), Jan. 2019.
• E. Birmelé, R. A. Ferreira, R. Grossi, A. Marino, N. Pisanti, R. Rizzi, and G. Sacomoto. Optimal listing of cycles and st-paths in undirected graphs. In Proc. SODA 2013, pages 1884-1896, 2013.
• M. Brazil. Steiner Minimum Trees in Uniform Orientation Metrics, pages 1-27. Springer US, Boston, MA, 2001.
• J. Byrka, F. Grandoni, T. Rothvoss, and L. Sanità. Steiner Tree Approximation via Iterative Randomized Rounding. J. ACM, 60(1), 2013.
• Y. Cao. Enumerating Maximal Induced Subgraphs. CoRR, abs/2004.09885, 2020.

タイトルに関連する用語 (4件)： 問題 ,  多項式 ,  遅延 ,  エミュレーション