λ-幾何における3点の最小スタミナ木のスタイナ点位置
スポンサーリンク
概要
- 論文の詳細を見る
スタイナ木は, x-y平面上に与えられた点の集合に必要に応じて新たな点(スタイナ点と呼ぶ)を追加して, 点間を枝で接続した木である.特に, 枝の長さの和が最小になる木を「最小スタイナ木」という.最小スタイナ木問題は, ネットワーク配置やVLSIの配線の最短経路問題として発展してきた.前者は, 任意芳香の線分を許すユークリッド幾何における最短経路を求める問題であり, 後者は, 水平芳香と垂直芳香の線分のみを許す直交幾何における最短経路を求める問題である.ユークリッド幾何と直交幾何の間を埋める「λ-幾何」は, 線分の方向を水平方向とπ/λ(λ≥2)の整数倍の方向にみに限定した幾何である.本論文では, 任意に与えられた3点に対するλ-幾何の最小スタイナ木のスタイナ点の位置の厳密解を示した.3点に対する最小スタイナ木のスタイナ点はたかだか1個であるので, スタイナ点の位置を決めれば最小スタイナ木は決まる.まず, 最小スタイナ木のスタイナ点の位置と3点の位置関係を示した.そして, λ≡0(mod3)の場合には, 最小スタイナ木のスタイナ点の候補位置が, 驚くことに無限個あり得ることを示した.次いで, 最小スタイナ木の枝長和が最小全域木と一致する場合, 及び, 最小スタイナ木の枝長和が最小全域木より小さくなる場合の3点の位置関係も示した.
- 社団法人電子情報通信学会の論文
- 1998-12-25
著者
関連論文
- D-7-12 動画像による健常者の膝関節運動機能解析法の検討(D-7. MEとバイオサイバネティックス,一般セッション)
- リングセグメント型Globally Asynchronous Locally Synchronous Systemの構成法(ネットワークオンチップ,システムオンシリコンを支える設計技術)
- モデル検査ツールUPPAALを用いたGALSシステムの形式的検証(ネットワークオンチップ,システムオンシリコンを支える設計技術)
- 記号モデル検査を用いた状態マシン図とシーケンス図の無矛盾性の検証(設計支援)
- 有界モデル検査を用いた複数UML図の形式的検証
- D-3-3 有界モデル検査を用いた複数UML図の検証に関する検討(D-3.ソフトウェアサイエンス,一般講演)
- Globally Asynchronous Locally Synchronous Systemの性能評価に関する一検討(上流設計技術(2),システムオンシリコン設計技術並びにこれを活用したVLSI)
- 射影変換の高速化に関する一検討(演算回路/専用回路,システムオンシリコン設計技術並びにこれを活用したVLSI)
- K_067 透視化機能をもつマルチウィンドウシステムの高解像度化(K分野:ヒューマンコミュニケーション&インタラクション)
- B_003 シーケンス図と状態遷移図で記述されたUMLモデルを対象としたモデル検査による形式的検証(B分野:ソフトウェア)
- D-11-97 漸化式表現による再構成型幾何学変換器(D-11.画像工学D(画像処理・計測),一般講演)
- D-11-64 多眼カメラによるモザイク動画像生成に関する研究(D-11.画像工学D(画像処理・計測),一般講演)
- D-10-1 モデル検査手法を用いたUML図の検証(D-10.ディペンダブルコンピューティング,一般講演)
- C-024 ウィンドウの透視化と輝度低下機能を持つマルチウィンドウシステムの評価(C分野:アーキテクチャ・ハードウェア)
- D-11-69 射影変換を対象としたDRAM-SRAM間画像転送法(D-11. 画像工学B(画像デバイス・装置), 情報・システム2)
- D-11-27 RISC命令の並列実行機能を有する画像処理用DSP(D-11. 画像工学A(画像基礎・符号化), 情報・システム2)
- C-019 操作対象ウィンドウの透視化機能を持つマルチウィンドウシステム(C.アーキテクチャ・ハードウェア)
- A-4-27 大規模ディジタルシステムのSTPNによるモデル化(A-4. ディジタル信号処理)
- D-10-14 メタステーブル動作を考慮したリングアービタのペトリネット表現
- 半構造データにおけるスキーマ抽出問題の計算複雑さ
- D-6-6 高速マルチウィンドウシステムのハードウエアアーキテクチャ
- オブジェクト指向データベースにおける逆行を含む属性集合とその閉包を用いた経路式を経由するクラスの一探索法
- グラフデータベースにおける正規表現及び文脈自由文法を満たす最短経路の一探索法
- Globally Asynchronous Locally Synchronous Systemの性能評価に関する一検討(上流設計技術(2),システムオンシリコン設計技術並びにこれを活用したVLSI)
- 射影変換の高速化に関する一検討(演算回路/専用回路,システムオンシリコン設計技術並びにこれを活用したVLSI)
- λ-幾何における3点の最小スタミナ木のスタイナ点位置
- λ-幾何(λ=3m)のスタイナ木の作成法
- $\lambda$-幾何における3点の最小スタイナ木について(計算理論とその応用)
- λ-幾何のスタイナ木作成法
- λ-幾何のスタイナ木作成法
- トランスダクション法向け論理回路マッパ
- 移動分散データベースにおける質問処理
- 移動分散データベースにおける質問処理