| 作成者 |
|
|
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
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.続きを見る
|
Mendeley出力
116.ps.tar
116.ps