文献

J-GLOBAL ID：201402224568254870   整理番号：14A1500224

順列決定グラフ(πDD)を用いたオイラー路の高速な列挙索引化

Fast Indexing All Eulerian Trails Using Permutation Decision Diagrams

著者 (2件)： 井上祐馬 (北大 大学院情報科学研究科) ,  湊真一 (北大 大学院情報科学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 114  号： 238(COMP2014 25-31)  ページ： 25-29  発行年： 2014年10月01日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： オイラー路とは,グラフ上の全ての辺をちょうど1度だけ通る路である。無向グラフにおけるオイラー路の数え上げ問題は#P完全であるが,動的計画法により比較的効率よく計算できる。本稿ではオイラー路が辺の順列であることに着目し,順列集合を扱える決定グラフを用いて,全てのオイラー路の列挙索引化を行う。決定グラフの構築アルゴリズムに動的計画法を応用することで,数え上げと同等の時間での列挙索引化を可能にする。(著者抄録)

シソーラス用語： *グラフ ,  無向グラフ ,  動的計画法 ,  *順列 ,  計算機シミュレーション ,  *索引
準シソーラス用語： 計算機実験

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

引用文献 (8件)：

• L. Euler, "Solutio problematis ad geometriam situs pertinentis,″ Commentarii academiae scientiarum Petropolitanae, vol.8, pp.128-140, 1741.
• P.A. Pevzner, H. Tang, and M.S. Waterman, "An Eulerian path approach to DNA fragment assembly," Proceedings of the National Academy of Sciences, vol.98, no.17, pp.9748-9753, 2001.
• K. Roy, "Optimum gate ordering of CMOS logic gates using Euler path approach: Some insights and explanations," Journal of Computing and Information Technology, vol.15, no.1, pp.85-92, 2007.
• C. Hierholzer and C. Wiener, "Über die möglichkeit, einen limenzug ohne wiederholung und ohne unterbrechung zu umfahren," Mathematische Annalen, vol.6, no.1, pp.30-32, 1873.
• G.R. Brightwell and P. Winkler, "Note on counting eulerian circuits,″ Technical report, Centre for Discrete and Applicable Mathematics, London School of Economics, 2004.

タイトルに関連する用語 (3件)： 順列 ,  グラフ ,  索引