階層グラフ描画におけるダミー頂点の共有(アルゴリズムとデータ構造・計算複雑度)
スポンサーリンク
概要
- 論文の詳細を見る
グラフの階層描画において,連続しない階層上の頂点を結ぶ辺の上にはダミー頂点が設けられる.本論文では,まず,ダミー頂点を複数の辺に共有させる単純なアルゴリズムを提案し,計算機実験により,それがグラフを簡潔なものにするために有効であることを示す.ダミー頂点の共有を許す場合,処理後のグラフの頂点数や辺の本数をできるだけ少なくすることが望まれる.本研究では,問題の入力を連結3階層グラフに限定した場合でも,頂点数を最小化する問題及び辺数を最小化する問題がNP困難であることを示す.
- 2011-12-01
著者
-
山口 一章
神戸大学
-
山口 一章
神戸大学大学院 工学研究科
-
山口 一章
神戸大学大学院工学研究科
-
増田 澄男
神戸大学大学院工学研究科
-
荒木 徹也
神戸大学大学院工学研究科
-
山口 一章
神戸大学大学院
-
増田 澄男
神戸大学大学院
関連論文
- D-1-2 グラフ描画アルゴリズムに基づいたデフォルメ路線図作成法(D-1. コンピュテーション, 情報・システム1)
- BD木を用いたマルチレイヤデータ管理構造の改良
- 空間に埋め込まれた木の距離とその計算法
- 類似データ検索のためのファイル構成法
- 引出し線を用いたラベル配置
- 引出し線を用いた地図ラベル配置アルゴリズム
- D-1-8 地図中の地点と線情報へのラベル配置のためのラベル候補作成法(D-1.コンピュテーション,一般講演)
- D-1-3 優先度付き地図ラベル配置アルゴリズムの改良(D-1.コンピュテーション,一般講演)
- 地点の優先度を考慮した地図ラベル配置アルゴリズム
- グラフ描画へのラベル配置アルゴリズムの実験的評価
- グラフ描画へのラベル配置アルゴリズムの実験的評価
- D-1-1 優先度付き地図ラベル配置問題に対するラベル候補作成法(D-1. コンピュテーション, 情報・システム1)
- 辺がラベルをもつ無向グラフの描画法(グラフとネットワーク)
- D-1-2 辺がラベルをもつグラフの描画アルゴリズム
- グラフ描画における辺のラベルの配置法
- グラフ描画における辺のラベルの配置法
- D-1-10 引出し線を用いたラベル配置アルゴリズムの改良(D-1.コンピュテーション,一般講演)
- グラフ描画の直交格子への埋込アルゴリズムとデフォルメ路線図作成への応用(グラフとネットワーク)
- ラベル配置可能領域とルール処理を用いたラベル配置アルゴリズム(研究速報)
- D-4-14 複数の参照点による距離近似を用いた類似検索手法の提案
- 有向グラフ描画アルゴリズムにおける閉路削除法の改良
- 5M-8 点パターン検索のためのアルゴリズムの提案(アルゴリズム,学生セッション,ソフトウェア科学・工学)
- 局所探索法による階層的描画の辺交差削減(研究速報)
- 一般化したラベルサイズ最大化問題に対するアルゴリズム(研究速報)
- 力指向グラフ描画アルゴリズムにおける頂点移動方法の改良(研究速報)
- D-1-5 有向グラフ描画アルゴリズムにおける閉路削除法の改良(D-1. コンピュテーション,一般セッション)
- D-1-11 図形データの重なり判定を高速化するデータ構造の提案(D-1.コンピュテーション,一般講演)
- D-1-9 二次元点パターンマッチング問題に対する高速なアルゴリズム(D-1.コンピュテーション,一般講演)
- 地理データに対する領域隣接グラフを利用した領域管理手法(研究速報)
- TLAESAに基づく近似κ近傍検索手法(研究速報)
- ラベル配置問題の厳密解法の提案
- 最大重みクリークを効率良く抽出するための頂点系列の生成法
- 最大重みクリークの重みの上界の高速な計算法
- D-4-9 類似検索手法TLAESAの改良(D-4. データ工学, 情報・システム1)
- D-4-8 地理データに対する領域管理手法の実験的評価(D-4. データ工学, 情報・システム1)
- D-1-3 頂点がグループ分けされた階層的グラフの描画法(D-1. コンピュテーション, 情報・システム1)
- Comparability supergraphを用いた最大重みクリーク問題の厳密解法
- Chordal SupergraphとChordal Subgraphによる最大クリーク問題の緩和問題構成法について
- A-34 グラフ最適化問題に対する緩和問題の構成法の提案(最適化,A.アルゴリズム・基礎)
- D-1-3 グラフの最大独立頂点集合数の上界の計算法の提案
- グラフ描画における頂点ラベルの配置法
- 類似検索手法による無向グラフの最短経路探索法
- 階層グラフ描画におけるダミー頂点の共有(アルゴリズムとデータ構造・計算複雑度)
- 階層グラフ描画における頂点座標決定アルゴリズム(グラフとネットワーク)
- 全頂点のラベルを配置したグラフ描画を求めるアルゴリズム(グラフとネットワーク)
- 電気関係学会関西支部連合大会 : 特集号によせて
- 電気関係学会関西支部連合大会 : 特集号によせて
- 文字列の縦書きと折返しを許したラベル配置アルゴリズム(研究速報)
- 動的計画法を用いた有向二値完全系統樹の効率のよい列挙
- 動的計画法を用いた上界計算法による最大重みクリーク抽出アルゴリスムの提案(一般)
- 動的計画法を用いた有向二値完全系統樹の効率のよい列挙(一般)
- 階層グラフの直交描画アルゴリズム
- 階層グラフの直交描画アルゴリズム(グラフとネットワーク)