<テクニカルレポート>
Taking a Walk on a Graph

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 A walk on an edge-colored graph G is a path in G which contains each edge at least once, and the trace of a walk w is the sequence of edge-colors seen in w. We investigate the walk realizability probl...em, which is to decide, given an edge-colored graph G and a string x of colors, if there is a walk on G with trace x. We define a method of decomposing graphs into linear chains, and show that the number of the linear chains in the decomposition is a key to the complexity of the walk realizability problem. The problem is shown to be in NLOG for the following classes of graphs: (i) undirected graphs decomposable into a constant number of linear chains, (ii) trees decomposable into O(log m) linear chains, where m is the number of edges, (iii) directed graphs decomposable into O(log m) linear chains. However, the problem for trees, some of which are decomposable into \theta(m) linear chains, turns to be NP-complete even for (1,1)-caterpillars which are trees of a very simple form.続きを見る

本文情報を非表示

116.ps.tar pdf 178 KB 41  
116.ps tgz 131 KB 4  

詳細

レコードID
査読有無
関連情報
タイプ
登録日 2009.04.22
更新日 2017.01.20