A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs  

作　　者：Shin-ichi Nakano Ryuhei Uehara Takeaki Uno 

机构地区：[1]Department of Computer Science,Faculty of Engineering,Gunma University,Gunma 376-8515,Japan [2]School of Information Science,Japan Advanced Institute of Science and Technology,Ishikawa 923-1292,Japan [3]National Institute of Informatics,Tokyo 101-8430,Japan

出　　处：《Journal of Computer Science & Technology》2009年第3期517-533,共17页计算机科学技术学报（英文版）

基　　金：presented at the 4th Annual Conference on Theory and Applications of Models of Computation(TAMC07)

摘　　要：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（nlogn）） of the number of distance-hereditary graphs and cographs to 2^[3.59n] and 2^3n, respectively.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（nlogn）） of the number of distance-hereditary graphs and cographs to 2^[3.59n] and 2^3n, respectively.

关 键 词：algorithmic graph theory COGRAPH distance-hereditary graph prefix tree tree representation 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] Q343[自动化与计算机技术—计算机科学与技术]