Enumerating Eulerian Trails via Hamiltonian Path Enumeration

详细信息    查看全文

• 作者：Hiroyuki Hanada (17)
  Shuhei Denzumi (18)
  Yuma Inoue (18)
  Hiroshi Aoki (18)
  Norihito Yasuda (17)
  Shogo Takeuchi (17)
  Shin-ichi Minato (17) (18)
  
• 关键词：Eulerian trail ; Hamiltonian path ; path enumeration ; line graph ; zero ; suppressed binary decision diagram
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：8973
• 期：1
• 页码：161-174
• 全文大小：455 KB
• 参考文献：1. Wilson, R.J.: Introduction to Graph Theory, 4th edn. Pearson Education (1996)
  2. Harary, F.: Graph Theory, 1st edn. Addison-Wesley (1969)
  3. Mihail, M., Winkler, P.: On the number of Eulerian orientations of a graph. In: Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1992, pp. 138鈥?45 (1992)
  4. Creed, P.: Sampling Eulerian orientations of triangular lattice graphs. Journal of Discrete Algorithms聽7(2), 168鈥?80 (2009) CrossRef
  5. Ge, Q., 艩tefankovi膷, D.: The complexity of counting Eulerian tours in 4-regular graphs. Algorithmica聽63(3), 588鈥?01 (2012) CrossRef
  6. Kasteleyn, P.W.: A soluble self-avoiding walk problem. Physica聽29(12), 1329鈥?337 (1963) CrossRef
  7. Rubin, F.: A search procedure for Hamilton paths and circuits. Journal of the ACM聽21(4), 576鈥?80 (1974) CrossRef
  8. Mateti, P., Deo, N.: On algorithms for enumerating all circuits of a graph. SIAM Journal on Computing聽5(1), 90鈥?9 (1976) CrossRef
  9. van der Zijpp, N.J., Catalano, S.F.: Path enumeration by finding the constrained k-shortest paths. Transportation Research Part B: Methodological聽39(6), 545鈥?63 (2005) CrossRef
  10. Liu, H., Wang, J.: A new way to enumerate cycles in graph. In: International Conference on Internet and Web Applications and Services/Advanced International Conference on Telecommunications, p.聽57 (2006)
  11. Minato, S.-i.: Zero-suppressed BDDs and their applications. International Journal on Software Tools for Technology Transfer聽3(2), 156鈥?70 (2001)
  12. Diestel, R.: Graph Theory, 4th edn. Springer (2010)
  13. Chartrand, G.: On Hamiltonian line-graphs. Transactions of the American Mathematical Society聽134, 559鈥?66 (1968) CrossRef
  14. Harary, F., Nash-Williams, C.S.J.A.: On Eulerian and Hamiltonian graphs and line graphs. Canadian Mathematical Bulletin聽8, 701鈥?09 (1965) CrossRef
  15. Knuth, D.E.: 7.1.4 Binary Decision Diagrams. In: Combinatorial Algorithms, vol. 4A. The Art of Computer Programming, vol.聽4A. Pearson Education (2011)
  16. Knuth, D.E.: Don Knuth鈥檚 home page, http://www-cs-staff.stanford.edu/~uno/
  17. Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers聽C-35(8), 677鈥?91 (1986) CrossRef
  18. Inoue, T., Iwashita, H., Kawahara, J., Minato, S.: Graphillion: Software library designed for very large sets of graphs in python. Technical Report TCS-TR-A-13-65, Division of Computer Science, Hokkaido University (2013)
  19. Elkies, N., Kuperberg, G., Larsen, M., Propp, J.: Alternating-sign matrices and domino tilings (part I). Journal of Algebraic Combinatorics聽1(2), 111鈥?32 (1992) CrossRef
  
• 作者单位：Hiroyuki Hanada (17)
  Shuhei Denzumi (18)
  Yuma Inoue (18)
  Hiroshi Aoki (18)
  Norihito Yasuda (17)
  Shogo Takeuchi (17)
  Shin-ichi Minato (17) (18)
  
  17. ERATO Minato Discrete Structure Manipulation System Project, Japan Science and Technology Agency, Sapporo, Hokkaido, Japan
  18. Graduate School of Information Science and Technology, Hokkaido University, Sapporo, Hokkaido, Japan
  
• 丛书名：WALCOM: Algorithms and Computation
• ISBN：978-3-319-15612-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

Given an undirected graph G, we consider enumerating all Eulerian trails, that is, walks containing each of the edges in G just once. We consider achieving it with the enumeration of Hamiltonian paths with the zero-suppressed decision diagram (ZDD), a data structure that can efficiently store a family of sets satisfying given conditions. First we compute the line graph L(G), the graph representing adjacency of the edges in G. We also formulated the condition when a Hamiltonian path in L(G) corresponds to an Eulerian trail in G because every trail in G corresponds to a path in L(G) but the converse is not true. Then we enumerate all Hamiltonian paths in L(G) satisfying the condition with ZDD by representing them as their sets of edges.