TCS-TR-B-15-10

Date: Thu Feb 26 09:02:52 2015

Title: Master's Thesis: A Fast Algorithm for Enumerating Eulerian Paths

Authors: Muhammad Kholilurrohman

Contact:

First name: Muhammad
Last name: Kholilurrohman
Address: Graduate School of Information Science and Technology, Hokkaido University, North 14 West 9, Sapporo, 060- 0814, Japan
Email: kholil@ist.hokudai.ac.jp

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