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

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

タイトル: Bounding the Number of Reduced Trees, Cographs, and Series-Parallel Graphs by Compression
著者: Uno, Takeaki
Uehara, Ryuhei
Nakano, Shin-ichi
キーワード: cograph
compact representation
counting
encoding/decoding scheme
series-parallel graph, unordered reduced tree
発行日: 2013-06-21
出版者: World Scientific Publishing
誌名: Discrete Mathematics, Algorithms and Applications
巻: 5
号: 2
開始ページ: 1360001-1
終了ページ: 1360001-14
DOI: 10.1142/S179383091360001X
抄録: We give an efficient encoding and decoding scheme for computing a compact representation of a graph in one of unordered reduced trees, cographs, and series-parallel graphs. The unordered reduced trees are rooted trees in which (i) the ordering of children of each vertex does not matter, and (ii) no vertex has exactly one child. This is one of basic models frequently used in many areas. Our algorithm computes a bit string of length 2l-1 for a given unordered reduced tree with l >= 1 leaves in O(l) time, whereas a known folklore algorithm computes a bit string of length 2n -2 for an ordered tree with n vertices. Note that in an unordered reduced tree l <= n< 2l holds. To the best of our knowledge this is the first such a compact representation for unordered reduced trees. From the theoretical point of view, the length of the representation gives us an upper bound of the number of unordered reduced trees with l leaves. Precisely, the number of unordered reduced trees with l leaves is at most 2^<2l-2> for l >=1. Moreover, the encoding and decoding can be done in linear time. Therefore, from the practical point of view, our representation is also useful to store a lot of unordered reduced trees efficiently. We also apply the scheme for computing a compact representation to cographs and series-parallel graphs. We show that each of cographs with n vertices has a compact representation in 2n-1 bits, and the number of cographs with n vertices is at most 2^<2n-1>. The resulting number is close to the number of cographs with n vertices obtained by the enumeration for small n that approximates C d^n/n^<3/2>, where C=0.4126… and d=3.5608…. Series-parallel graphs are well investigated in the context of the graphs of bounded treewidth. We give a method to represent a series-parallel graph with m edges in (2.5285m-2) bits. Hence the number of series-parallel graphs with m edges is at most 2^<2.5285m-2>. As far as the authors know, this is the first non-trivial result about the number of series-parallel graphs. The encoding and decoding of the cographs and series-parallel graphs also can be done in linear time.
Rights: Electronic version of an article published as Discrete Mathematics, Algorithms and Applications, 5(2), 2013, 1360001-1-1360001-14. DOI:10.1142/S179383091360001X. Copyright World Scientific Publishing Company, http://dx.doi.org/10.1142/S179383091360001X
URI: http://hdl.handle.net/10119/11644
資料タイプ: author
出現コレクション:b10-1. 雑誌掲載論文 (Journal Articles)

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

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

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

 


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