A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
スポンサーリンク
概要
- 論文の詳細を見る
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.
論文 | ランダム
- 漁村児童の不衛生ととりくむ--子どもとともに伸びる教師の実践
- 結晶質岩を対象とした放射性核種の移行・遅延モデルの構築と妥当性評価--Nagra/JNC原位置試験研究の概要
- 8-5.国別エネルギー消費量と産業構造の関連の分析(3)((2)温室効果ガス削減・エネルギーモデル,Session 8 エネルギー評価・経済)
- 8-12.国別エネルギー消費量と産業構造の関連の分析(2)((3)ライフスタイル・産業構造,Session 8 エネルギー評価・経済)
- 9-10.国別エネルギー消費量と産業構造の関連の分析((4)国際エネルギー需給,Session 9 エネルギー評価・経済)