講演抄録/キーワード |
講演名 |
2014-10-08 15:15
順列決定グラフ(πDD)を用いたオイラー路の高速な列挙索引化 ○井上祐馬・湊 真一(北大) COMP2014-30 |
抄録 |
(和) |
オイラー路とは,グラフ上の全ての辺をちょうど1度だけ通る路である.
無向グラフにおけるオイラー路の数え上げ問題は#P完全であるが,動的計画法により比較的効率よく計算できる.
本稿ではオイラー路が辺の順列であることに着目し,順列集合を扱える決定グラフを用いて,全てのオイラー路の列挙索引化を行う.
決定グラフの構築アルゴリズムに動的計画法を応用することで,数え上げと同等の時間での列挙索引化を可能にする. |
(英) |
An Eulerian trail is a trail containing all edges of a given graph exactly once.
Although counting problem of Eulerian trails on an undirected graph is #P-Complete,
a dynamic programming approach can solve this problem much better.
In this paper, since an Eulerian trail can be represented as a permutation of edges,
we enumerate and index all Eulerian trails by using permutation decision diagrams.
We realize decision diagram construction as fast as counting
by applying the dynamic programming approach to our construction algorithm for a decision diagram. |
キーワード |
(和) |
グラフ / オイラー路 / 列挙 / 動的計画法 / 順列決定グラフ / / / |
(英) |
Graph / Eulerian Trail / Enumeration / Dynamic Programming / Permutation Decision Diagrams / / / |
文献情報 |
信学技報, vol. 114, no. 238, COMP2014-30, pp. 25-29, 2014年10月. |
資料番号 |
COMP2014-30 |
発行日 |
2014-10-01 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2014-30 |