プトレマイオスグラフのラミナー構造とその応用
スポンサーリンク
概要
- 論文の詳細を見る
任意の4頂点がトレミーの不等式を満たすグラフのことをプトレマイオスグラフと呼ぶ.このグラフのクラスは, 距離に関して遺伝性を持つ弦グラフのクラスと一致する.一方, このグラフのクラスはブロックグラフや木の自然な一般化でもある.本稿ではクリークのラミナー構造によるプトレマイオスグラフの新しい特徴づけを与える.この構造は木による表現を持つ.この木表現は, プトレマイオスグラフに対する単純な交差モデルも与える.さらにこの木表現は, 辞書式順序幅優先探索による完全点消去スキームから, 線形時間で計算することができる.したがって, 認識問題と同型性判定問題を, どちらも線形時間で解くことができる.さらにこの木表現を応用し, ハミルトン閉路問題を解くO(n)時間アルゴリズムを示す.
- 社団法人電子情報通信学会の論文
- 2005-09-08
著者
-
上原 隆平
北陸先端科学技術大学院大学
-
宇野 裕之
大阪府立大学理学系研究科
-
上原 隆平
北陸先端科学技術大学院大学情報科学研究科
-
上原 隆平
北陸先端科学技術大学情報科学研究科
-
宇野 裕之
大阪府立大学理学系研究科情報数理科学専攻
-
宇野 裕之
大阪府立大学
-
上原 隆平
北陸先端科学技術大学院大学情報科学
関連論文
- 区間二部グラフの効率の良い認識に関する研究 (アルゴリズムと計算機科学の数理的基盤とその応用)
- 1-D-4 経路長を短くする一方通行決定(離散・組合せ最適化(2))
- Bipartite Permutation Graphのランダム生成と列挙
- 弦グラフおよび弦二部グラフのクラスにおけるマッチングの数え上げ
- 再構成問題の計算複雑さ
- あみだくじの高速列挙
- 折紙の計算量的複雑さの研究 (小特集 折紙工学の現状と課題)
- 2-D-19 最長路問題に対する次数2以下の点の除去処理とその分枝限定法での利用(離散最適化)
- 折紙の計算量的複雑さの研究(折紙工学の現状と課題)
- Complexity of pleat folding (理論計算機科学の深化と応用--RIMS研究集会報告集)
- Enumeration of Perfect Sequences of Chordal Graph (Acceleration and Visualization of Computation for Enumeration Problems)
- Polygons Folding to Plural Incongruent Orthogonal Boxes (Acceleration and Visualization of Computation for Enumeration Problems)
- Reconstruction of Connected Interval Graphs (Acceleration and Visualization of Computation for Enumeration Problems)
- 2-E-17 Enumeration of Perfect Sequences of Chordal Graph
- じゃばら折りの複雑さに関する研究
- 2-E-6 無限サーバ待ち行列がつくるスケールフリー区間グラフ : クラスタ係数の評価(待ち行列(2))
- 複数の箱を折ることのできる展開図に関する研究
- 折り紙とコンピュータサイエンス(学生/教養のページ)
- コーダルグラフの完全列の列挙
- 2-B-4 無限サーバ待ち行列がつくるスケールフリー区間グラフ(待ち行列(2))
- 区間表現からMPQ-treeを効率よく構成するアルゴリズム
- 区間表現からMPQ-tree を効率よく構成するアルゴリズム(計算機科学の理論とその応用)
- スケールフリーグラフ上における局所情報を用いたランダムウォークについて
- 2部パーミュテーショングラフのバンド幅
- 航空路線問題に対する効率の良いアルゴリズム
- プトレマイオスグラフのラミナー構造とその応用
- ある限られたグラフクラスに対する最長路問題
- 部分ゲートとその同定
- 多くの計算路によって特徴付られる計算量クラス
- 絵画的迷路の作り方 (理論計算機科学の深化と応用)
- 距離遺伝的グラフの木表現とその応用
- コーダルグラフの独立点集合の数えあげ問題
- Canonical Data Structure for Probe Interval Graphs (Evolutionary Advancement in Fundamental Theories of Computer Science)
- プロープ区間グラフの拡張MPQ木表現
- 2部グラフとProbe区間グラフにおける木スパナー
- 2部グラフの部分クラスに対するGI完全性について
- 重み最大マッチングを求める並列近似アルゴリズム
- グラフの連結成分の個数と応用
- 弦グラフの一般化と、そのグラフ上での問題の難しさ
- ある投票ゲームのシミュレーション
- Ptolemaic Graph 上の最長路問題に関する研究(計算機科学の理論とその応用)
- 飛び出す絵本の複雑さ
- 単純多角形の生成に関する発見的手法(セッション2)
- グラフ上のボロノイゲームとその困難性(セッション1)
- 3充足可能性判定問題3SATの単一解を持つ正例題生成手法
- 3充足可能性判定問題 3SAT の単一解を持つ正例題生成手法の解析
- Investigating Web Structure by Cliques and Stars (Acceleration and Visualization of Computation for Enumeration Problems)
- 2-F-11 An O(n log^2 n)-Time Algorithm for L(2,1)-Labeling of Trees
- RA-002 木のL(2,1)-ラベリングのためのO(n log^2 n)時間アルゴリズム(モデル・アルゴリズム・プログラミング,査読付き論文)
- 木のL(2,1)-ラベリングに対するO(n^)時間アルゴリズム
- ウェブグラフ : その性質と利用(OR研究の最前線)
- 2-C-6 最長路問題に対する2連結成分分解にもとづく分枝限定法による厳密解法(グラフ・ネットワーク(1))
- 複数の交叉演算による遺伝的アルゴリズムの改良(2)交叉演算を選択するファジィルールの改良
- 複数の交叉演算による遺伝的アルゴリズムの改良
- ファジィ決定木生成法 ファジィC4.5とその改良(その3) : 修正利得のパラメータを節点の深さとデータ数に応じて変化させる方法
- ファジィ索引とその類似データに基づく推論への応用
- ファジィ決定木生成法 ファジィC4.5とその改良(その2) : 節点に応じて修正利得を変化させる方法
- 幾何図形におけるアナロジーへのファジィ理論の応用 : 図形の変化の階層的決定法
- 木の(p, q)-全ラベリング問題
- 帯状の紙の折りたたみに関する最適化問題
- 正4面体と他の正多面体との共通の辺展開図に関する研究
- 一般化KaboozleのNP完全性
- 折紙における決定不能問題
- 孤立クリークおよび孤立スター縮約ウェブグラフにおけるウェブ構造マイニング
- 外平面的グラフの(2,1)-全ラべリング数のタイトな上界
- パス上のボロノイゲーム
- 帯状の紙の折りたたみに関する最適化問題
- 折紙における決定不能問題
- 一般化 Kaboozle のNP完全性
- 閾グラフの最小辺ランキング全域木について
- プトレマイオスグラフのラミナー構造とその応用
- ルールの生成法と推論法を変化させる学習の拡張
- 幾何図形におけるアナロジーへのファジィ理論の応用
- 木のL(2, 1)-ラベリングに対する線形時間アルゴリズム
- 最小辺ランキング全域木問題について
- On Minimum Edge Ranking Spanning Trees
- ランダム有向グラフにおける到達可能性と推移閉包の大きさについて
- 関係の推移閉包の大きさの近似的推定法
- ルールの生成法と推論法を変化させる学習の拡張 : 保有するデータ数を制限する場合
- k-木のスケールフリー性に関する研究
- k-木のスケールフリー性に関する研究
- ファジィ索引とその類似データ検索への応用
- UNO は一人でも難しい (計算機科学とアルゴリズムの数理的基礎とその応用)
- 正4面体と正6面体との共通の展開図の構成に関する研究
- 等間隔の折り目を持つ紙の折り畳みの計算量について
- 複数の単位円による点集合の排他的被覆
- Hoffmanパズル解の列挙と一般化に関する研究
- 複数の直方体を折れる共通の展開図に関する研究
- グラフクラスとアルゴリズム
- 複数の直方体を折れる共通の展開図に関する研究
- ゲーム・パズルの計算量を示すための新しい枠組みについて(パズルとゲームの計算理論)
- On the base-line location problem for the maximum weight region decomposable into base-monotone shapes (New Trends in Algorithms and Theory of Computation)
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題
- ある投票ゲームのシミュレーション
- 単位正方形上の一意被覆問題に対する近似アルゴリズム
- トロミノ詰込問題の計算複雑さについて
- キャタピラグラフの独立点集合遷移問題に対する多項式時間アルゴリズム
- DS-1-11 Free Flood Filling Gameの計算複雑性について(DS-1.COMP学生シンポジウム,シンポジウムセッション)
- ペンシルパズル「シャカシャカ」の計算複雑さと整数計画モデル
- 基単調図形に分割可能な最大重み領域を得る基線の配置問題