| 講演抄録／キーワード |
| 講演名 |
2005-09-15 10:50
Laminar Structure of Ptolemaic Graphs and Its Applications
○Ryuhei Uehara（JAIST）・Yushi Uno（Osaka Pref. Univ.） |
| 抄録 |
（和） |
任意の4頂点がトレミーの不等式を満たすグラフのことをプトレマイオスグラフと呼ぶ．
このグラフのクラスは，距離に関して遺伝性を持つ弦グラフのクラスと一致する．
一方，このグラフのクラスはブロックグラフや木の自然な一般化でもある．
本稿ではクリークのラミナー構造によるプトレマイオスグラフの新しい特徴づけを与える．
この構造は木による表現を持つ．
この木表現は，プトレマイオスグラフに対する単純な交差モデルも与える．
さらにこの木表現は，辞書式順序幅優先探索による完全点消去スキームから，
線形時間で計算することができる．
したがって，認識問題と同型性判定問題を，どちらも線形時間で解くことができる．
さらにこの木表現を応用し，ハミルトン閉路問題を解くO(n)時間アルゴリズムを示す． |
| （英） |
Ptolemaic graphs are graphs that satisfy the Ptolemaic inequality for any four vertices.
The graph class coincides with the intersection of chordal graphs and distance hereditary graphs.
The graph class can also be seen as a natural generalization of block graphs (and hence trees).
In this paper, a new characterization of ptolemaic graphs is presented.
It is a laminar structure of cliques, and leads us to a canonical tree representation.
The tree representation gives a simple intersection model for ptolemaic graphs.
The tree representation is constructed in linear time from
a perfect elimination ordering obtained by the lexicographic breadth first search.
Hence the recognition and the graph isomorphism for ptolemaic graphs can be solved in linear time.
Using the tree representation,
we also give an O(n) time algorithm for the Hamiltonian cycle problem. |
| キーワード |
（和） |
アルゴリズム的グラフ理論 / 交差モデル / データ構造 / ハミルトン閉路問題 / プトレマイオスグラフ / / / |
| （英） |
Algorithmic graph theory / data structure / Hamiltonian cycle / intersection model / ptolemaic graph / / / |
| 文献情報 |
信学技報, vol. 105, no. 273, COMP2005-30, pp. 17-24, 2005年9月. |
| 資料番号 |
COMP2005-30 |
| 発行日 |
2005-09-08 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|