TCS-TR-A-14-77

Date: Fri Oct 3 19:03:25 2014

Title: An Efficient Algorithm for Enumerating Eulerian Paths

Authors: Muhammad Kholilurrohman and Shin-ichi Minato

Contact:

  • First name: Shin-ichi
  • Last name: Minato
  • Address: Graduate School of Information Science and Technology, Hokkaido University, North 14 West 9, Sapporo, 060- 0814, Japan
  • Email: minato@ist.hokudai.ac.jp

Abstract. Although a mathematical formula for counting the number of Eulerian circles in a directed graph is already known [1, 2], no formula is yet known for enumerating such circles if the graph is an undirected one. In computer science, the latter problem is known to be in #P-complete, enumerating the solutions of such problem is known to be hard. In this paper, an ecient algorithm to enumerate all the Eulerian paths in an undirected graph, both simple graph and multigraph, is proposed.


©Copyright 2014 Authors