Combinatorial Generation

ISBN-13: 9783639232202 / Angielski / Miękka / 2010 / 56 str.

MD Shariful Islam Bhuyan

Opis

Efficient generation of combinatorial objects is a well-researched area. Among them many literature devoted on the combinatorial Gray code approach where the goal is to find a Hamiltonian path or cycle in a representative graph of the corresponding combinatorial class. Another approach namely genealogical tree approach has been recently introduced where the goal is to find a rooted spanning tree in the representative graph. Researchers have also focused on finding general patterns in the generation techniques of combinatorial classes so that common approaches can be applied to a large number of related problems. Here, we propose a unifying framework for combinatorial generation by giving recursive definition of an abstract combinatorial class. The definition can be instantiated to an array of specific combinatorial classes namely n-tuple, combination, integer partition, set partition and binary trees by specifying the framework parameters appropriately. As an illustration, we show the instantiation of the combinatorial class of n-tuples, combinations and balanced parenthesis strings and also give novel constant-time generation algorithm for each of them.

O autorze

Md. Shariful Islam Bhuyan is currently serving as an assistant professor in the Department of Computer Science and Engineering of Bangladesh University of Engineering and Technology. He received both his B.Sc. and M.Sc. degree in Computer Science and Engineering from the same department.