Luis Goddyn

What Luis has to say about himself
Status: CECM Member, Associate Professor
Affiliation: Department of Mathematics and Statistics, SFU
Phone: (604) 291-4699
Office: TLX10523


Research Interest

My research falls roughly into three areas: circuit and flow structure of graphs and matroids, specialized Gray codes, and Euclidean optimization problems. Each of these topics has benefited greatly from having computing support in the form of symbolic manipulation, numerical calculation and the generation of large combinatorial examples. In all three areas computer experimentation has revealed phenomena which would otherwise not have been visible.

There are close connections between circuit covers, colorings, flow theory, and graph embeddings. Recent results include a characterization of graphs and matroids whose circuits (as edge-sets) form a Hilbert basis, a connection between the star-chromatic number of a graph and flows in matroids, and progress toward the "edge choosability conjecture" for planar graphs.

Gray codes are commonly used in the design of position-digital converters and communication codes. A space-science application motivated me to investigate and construct specialized Gray codes with optimized run-length properties. Finding good codes involves careful computer searches to inspire direct constructions. As well as being of theoretical interest, the resulting codes have been used to greatly increase the resolution of the CODACON spectrometer being constructed at L.A.S.P., Univ. of Colorado for a satellite application.

One of the most-studied optimization problems is the Euclidean Traveling Salesman Problem (ETSP). By proposing and analyzing heuristic algorithms, one can bound the worst-case and average-case instances of this problem. Using a heuristic base on quanizers, I have improved bounds in the worst-case analysis of ETSP. (Quantizers are used in information theory and communication as a way of digitizing blocks of information.) It appears likely that quantizers can similarly be used to improve the analysis of other optimization problems such as the Steiner Tree Problem and the Minimum Perfect Matching Problem.

Welcome to CECM
CECM Site Search

Advanced Search
Your name:

Your email address:

Your comments:
Permanent Members  |  Associate Members  |  Technical Associates  |  Visitors / Students  |  Past Members