An Efficient Tree-Generation Algorithm

Abstract

An algorithm for generation of trees of a connected, non-oriented, and simple graph is presented in this paper. The space complexity of the algorithm is independent of the number of trees and the time complexity is drastically reduced compared to the brute-force technique. The algorithm is easily programmable. Experimental results for several graphs are presented.

Indexing Terms:

• Graph
• Tree
• Complexity

Additional information

Notes on contributors

A. Rakshit

Rakshit, A: Obtained M.Sc. (Mathematics) degree from I.I.T. Kharagpur in 1976. In the same year, he joined the Computer Centre, University of Calcutta as a research fellow. Since August 1979 he was associated with the Computer Centre as a faculty, member. At present, he is a faculty member in the Department of Computer Science, Calcutta University, and is engaged in teaching and research in different branches of Computer Science. His present research interests include graph theory, data base management system and optimization problem related to different software systems.

S. Sen Sarma

Sen Sarma, S: Obtained B.Sc. (Physcis), B.Tech. (Applied Physics) and M.Tech. (Radio-physics and Electronics) degree from the University of Calcutta in 1969, 1972 and 1974 respectively. From 1975–77 he worked as a research scholar in the department of Radiophysics and Electronics. During 77–78 the author worked in the department of E & E C E (I.I.T. Kharagpur) as a project associate. In January ‘79 he became Lecturer in the department of Radiophysics and Electronics. From November ‘80 he is a faculty member in the newly created department of Computer Science, University of Calcutta. His area of research is theory and practice of Graph algorithms.

R. K. Sen

Sen, R K (Dr): Born in 1949, obtained M.Sc. with Electronics from Bombay University in 1973, Ph.D. in Radiophysics and Electronics from Calcutta University in 1978. Presently, in the faculty of Computer Centre, Indian Institute of Technology. Research interests include Graph Theory & Applications, Theory of Computations, Asynchronous System Design, Data Base Systems, Programming Languages and Computer Architecture. Member of the Association of Computing Machinery.