NC State University

Department of Computer Science Colloquia Series 1998-99

Date: Thursday, November 19, 1998
Time: 3: 30 PM (refreshments), 4:00 PM (talk)
Place: Withers 402A, NCSU Historical Campus (click for courtesy parking request)

Speaker: Dr. Carla Savage, Computer Science, NCSU

Combinatorial Gray Codes

Abstract: Many practical problems require for their solution the sampling of a random object from a combinatorial class or, worse, an exhaustive search through all objects in the class. However, in order for such a listing to be possible, even for objects of moderate size, combinatorial generation methods must be extremely efficient. The ``Gray code'' approach is to try to generate the objects as a list in which successive elements differ only in a small way. The classic example is the binary reflected Gray code which is a scheme for listing all $n$-bit binary numbers so that successive numbers differ in exactly one bit. The advantage anticipated by such an approach is that generation of successive objects might be faster. Although for many combinatorial families, a straightforward lexicographic listing algorithm requires only constant average time per element, for other families, such as linear extensions, such performance has only been achieved by a Gray code approach.
Aside from computational considerations, open questions in several areas of mathematics can be posed as Gray code problems. Gray codes frequently involve elegant recursive constructions which provide new insights into the structure combinatorial families.
In this talk, we survey the area of combinatorial Gray codes, describe recent results, variations, and trends, and highlight some open problems.

Short Bio: Carla Savage is currently a Professor in the Department of Computer Science at NCSU, where she joined the faculty in 1978. She worked in the area of parallel algorithm design for her Ph.D. thesis (Mathematics, University of Illinois 1977) and for the ten years following. Her research since 1988 has been in the areas of discrete mathematics and combinatorial algorithms. The focus has been on the structure of combinatorial objects and various schemes for listing and counting them, with particular emphasis on efficient computation, Gray codes, and relationships to problems in graph theory, group theory, and combinatorics. Recent work is on identities and asymptotics for various classes of integer partitions. The work has been supported, by grants from NSF and NSA, in some combination, over the past ten years.
Savage is on the editorial board of the SIAM Journal on Discrete Mathematics. In recent years, she has served as Vice Chair of the SIAM Activity Group on Discrete Mathematics (1993-96), Chair of the Steering Committee for the SODA Conference (1995-98), and on the program committees for the 1998 SIAM Conference on Discrete Mathematics and the 1999 SIAM Annual Meeting.

Colloquia Home Page.