Title :
Research on the Improvements on Atallah´s Algorithm: A New Improved Algorithm on Atallah
Author :
Liu Shan ; Cao Lijun ; Liu Maohua ; Liu Jinghui
Author_Institution :
Collag.e of Math. & Inf. Technol., Hebei Normal Univ. of Sci. & Technol., Qinhuangdao, China
Abstract :
In this paper, we give a new algorithm evolving from Atallah´s algorithm proposed in 1984, and we make many improvements: First, combining replaced sewing in order to simplify the third step, Second, we delete the fourth step. And we simplify the construction of the auxiliary graph, avoiding the second time to find Euler tour and the introduction of a mass storage array. The improvements make it quicker and simpler to find the Euler tour of an Euler graph, and the improvements don´t increase time and space complexity of Atallah´s algorithm.
Keywords :
computational complexity; graph theory; Atallah algorithm; Euler graph; Euler tour; auxiliary graph construction; mass storage array; space complexity; time complexity; Algorithm design and analysis; Arrays; Complexity theory; Corporate acquisitions; Merging; Parallel algorithms; euler partion; euler tour; spanning tree;
Conference_Titel :
Communications and Mobile Computing (CMC), 2011 Third International Conference on
Conference_Location :
Qingdao
Print_ISBN :
978-1-61284-312-4
DOI :
10.1109/CMC.2011.45
