JAIST Repository >
b. 情報科学研究科・情報科学系 >
b10. 学術雑誌論文等 >
b10-1. 雑誌掲載論文 >

このアイテムの引用には次の識別子を使用してください: http://hdl.handle.net/10119/9179

タイトル: A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
著者: Nakano, Shin-ichi
Uehara, Ryuhei
Uno, Takeaki
キーワード: algorithmic graph theory
cograph
distance-hereditary graph
prefix tree
tree representation
発行日: 2009
出版者: Springer
誌名: Journal of Computer Science and Technology
巻: 24
号: 3
開始ページ: 517
終了ページ: 533
DOI: 10.1007/s11390-009-9242-3
抄録: Algorithms used in data mining and bioinformatics have to deal with huge amount of data efficiently. In many applications, the data are supposed to have explicit or implicit structures. To develop efficient algorithms for such data, we have to propose possible structure models and test if the models are feasible. Hence, it is important to make a compact model for structured data, and enumerate all instances efficiently. There are few graph classes besides trees that can be used for a model. In this paper, we investigate distance-hereditary graphs. This class of graphs consists of isometric graphs and hence contains trees and cographs. First, a canonical and compact tree representation of the class is proposed. The tree representation can be constructed in linear time by using prefix trees. Usually, prefix trees are used to maintain a set of strings. In our algorithm, the prefix trees are used to maintain the neighborhood of vertices, which is a new approach unlike the lexicographically breadth-first search used in other studies. Based on the canonical tree representation, efficient algorithms for the distance-hereditary graphs are proposed, including linear time algorithms for graph recognition and graph isomorphism and an efficient enumeration algorithm. An efficient coding for the tree representation is also presented; it requires ⌈3.59n⌉ bits for a distance-hereditary graph of n vertices and 3n bits for a cograph. The results of coding improve previously known upper bounds (both are 2 ^<O(n log n)>) of the number of distance-hereditary graphs and cographs to 2^<⌈3.59n⌉> and 2^<3n> , respectively.
Rights: This is the author-created version of Springer, Shin-ichi Nakano, Ryuhei Uehara and Takeaki Uno, Journal of Computer Science and Technology, 24(3), 2009, 517-533. The original publication is available at www.springerlink.com, http://dx.doi.org/10.1007/s11390-009-9242-3
URI: http://hdl.handle.net/10119/9179
資料タイプ: author
出現コレクション:b10-1. 雑誌掲載論文 (Journal Articles)

このアイテムのファイル:

ファイル 記述 サイズ形式
13863.pdf216KbAdobe PDF見る/開く

当システムに保管されているアイテムはすべて著作権により保護されています。

 


お問い合わせ先 : 北陸先端科学技術大学院大学 研究推進課図書館情報係