Gray Codes, Efficient Generation, and Structure in Combinatorial Families

点击翻译按钮获取中文摘要

This award supports the research of Professor Savage to work in combinatorics. One of the fundamental problems in the area of combinatorial algorithms is that of efficiently generating items in a particular class in such a way that each item is generated exactly once. Asymptotic improvement in the efficiency of combinatorial generation requires not only good data structures and algorithm design techniques, but more often, some new insight into the structure of the combinatorial class involved. These structure questions are in the realm of well-known open problems in discrete mathematics, graph theory, group theory, and combinatorics. It is these type of problems that Professor Savage will address. The research is in the general area of combinatorics. Combinatorics attempts to find efficient methods to study how discrete collections can be organized. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, as in telephone systems, and the design of algorithms in computer science all deal with discrete objects, and this makes use of combinatorial research.