置換グラフ上における最小節点ランキング全域木問題を解くアルゴリズム

• Item type: SIG Technical Reports(1)
• 公開日: 2003-11-07
• タイトル: 置換グラフ上における最小節点ランキング全域木問題を解くアルゴリズム
• タイトル / 言語: en
• タイトル: An algorithm for solving the minimum vertex ranking spanning tree problem on permutation graphs.
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 徳島大学総合科学部自然システム学科数理科学
• 著者所属: 豊橋技術科学大学 知識情報工学系
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Sciences, Faculty of Integrated Arts and Sciences, The University of Tokushima
• 著者所属(英): en
• 著者所属(英): Department of Knowledge-Based Information Engineering, Toyohashi University of Technology
• 著者名: 中山, 慎一; 増山, 繁
• 著者名(英): Shin-Ichi, Nakayama; Shigeru, Masuyama
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 最小節点ランキング全域木問題とは，与えられたグラフG上において，節点ランキングが最小となる全域木を求める問題である．本論文では，置換グラフ上における，最小節点ランキング全域木問題を解くO(n^3)時間アルゴリズムを提案する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This paper proposes an O(n^3) time algorithm for solving the minimum vertex ranking spanning tree problem on a permutation graph.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2003, 号 110(2003-AL-092), p. 33-40, 発行日 2003-11-07
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会