| 講演抄録／キーワード |
| 講演名 |
2006-03-22 16:00
Canonical Tree Representation of Distance Hereditary Graphs with Applications
○Ryuhei Uehara（JAIST）・Takeaki Uno（NII） |
| 抄録 |
（和） |
導出部分グラフにおいても頂点間の距離が変わらないグラフを，距離遺伝的グラフと呼ぶ．
本論文では距離遺伝的グラフに関する木表現を提唱する．
また，その木表現を線形時間で構成するアルゴリズムも示す．
この結果，このグラフクラスに関する認識問題や同型性判定問題は線形時間で解くことができる．
この木表現はコンパクトなデータ構造として使うこともでき，
すべての「頂点順序による特徴づけ」を生成することもできる． |
| （英） |
The class of distance hereditary graphs consists of
the isometric graphs.
That is, for each pair of vertices,
its distance is invariant for any induced path in
a distance hereditary graph.
In the paper, a canonical tree representation of
a distance hereditary graph is proposed.
A linear time algorithm for computing the tree representation
is also presented.
Hence the recognition problem and the graph isomorphism problem
for the graph class can be solved in linear time.
The tree representation takes O(|V|) space for
a distance hereditary graph G=(V,E).
Hence it can be used as a compact data structure for the graph.
It is so informative that all pruning sequences,
which is a previously known characterization based on a vertex ordering,
can be generated from the tree representation efficiently. |
| キーワード |
（和） |
アルゴリズム的グラフ理論 / 距離遺伝的グラフ / 木表現 / 認識問題 / 同型性判定問題 / / / |
| （英） |
algorithmic graph theory / distance hereditary graph / tree representation / recognition problem / isomorphism problem / / / |
| 文献情報 |
信学技報, vol. 105, no. 679, COMP2005-61, pp. 31-36, 2006年3月. |
| 資料番号 |
COMP2005-61 |
| 発行日 |
2006-03-15 (COMP) |
| ISSN |
Print edition: ISSN 0913-5685 |
| PDFダウンロード |
|