系統樹最節約復元の部分木に関する最小性について
スポンサーリンク
概要
- 論文の詳細を見る
外点に付値された木構造が与えられたときに, その木の長さを最小化するような内点への値付け(最節約復元)を考える第1最節約復元問題について, その最節約復元すべてを求めるアルゴリズムは既に与えられているが, 一般に最節約復元の個数は木の頂点数で上界を定められない.各最節約復元に対して, 与えられた木をある外点で根付けしたとき, 各部分木の全長をどれだけ最小化しているかを示す指標として歪み指数(distortion index)及び歪み列(distortion sequence)を導入し, その基準の下での最節約復元全体の構造を明らかにする.具体的には, この基準の下で最適又は最悪な最節約復元の特徴付けとこれらを決定するためのアルゴリズム, 及びこの基準(順序)による最節約復元全体の半順序集合が下に完備な半束となることを示す.
- 社団法人電子情報通信学会の論文
- 2001-07-09
著者
関連論文
- 8-329 学生カルテを中核とした個別教育の実施と運用 : 東海大学福岡短期大学におけるe-Learningの取り組み((9)e-ラーニング-V)
- 7-212 東海大学福岡短期大学におけるe-Learningの実施とその特色について : 「学びの自由化と個別教育」の実現に向けて(オーガナイズドセッション「バーチャルユニバーシティ」)
- 帰納型プロダラムの機械学習システム『Bくん』
- ジャンプナンバー問題のニューラルネットワークを用いた解法について
- 決定リストによる動詞語義曖昧性の解消
- MPR束における「結び既約元」の数理的性質について (計算機科学基礎理論の新展開)
- 系統樹最節約復元の部分木に関する最小性について(LAシンポジウム(情報基礎理論ワークショップ)論文小特集)
- 系統樹最節約復元の部分木に関する最小性について
- 系統樹最節約復元の部分木に関する最小性についてII (計算理論とアルゴリズムの新展開)
- 系統樹最節約復元の部分木に関する最小性について : Some properties of the distortion index on all MPRs (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)
- 系統樹最節約復元束の完備分配性について (計算機科学の基礎理論 : 21世紀の計算パラダイムを目指して)