Bruce A. Reed

Canada Research Chair in Graph Theory

Tier 1 - 2001-11-01
McGill University
Natural Sciences and Engineering


Coming to Canada from

Centre National de Recherche Scientifique, France

Research involves

Development of algorithms to solve complex problems from the theory of graphs and networks.

Research relevance

To understand the structure of large, complex networks and analyze the connections within them.

Network Analysis and Design

Networks are essential to communications, whether the network is the actual structure of a telecommunications system, the World Wide Web or the series of wires on a microchip. Graphs provide an abstract model of network connectivity, and can be used to analyze and predict network performance, as well as to determine the most efficient way of routing traffic along a network. Graphs are used to model the connections in a phone network, the links between Web pages and the wiring diagrams of VLSI chips. While the basic tenets of graph theory date back to the nineteenth century, the complexity and size of networks like the World Wide Web and mobile telephone systems demand new developments so that the theory can be applied effectively.

Dr. Bruce Reed has made significant advances in applying probabilistic analysis to the challenge of determining optimal graph colouring - the assignment of paths followed between vertices, or nodes, on a network. As Canada Research Chair in Graph Theory, he will expand his work on graph colouring, seeking to obtain near-optimal colouring for multigraphs, as well as looking into solving some of the challenges related to frequency assignment for mobile telephone networks.

Another branch of his research will focus on solving practical problems related to VLSI microchip design using tree decompositions and dynamic programming.

A third focus will be on random graphs, with particular emphasis on how they can be applied to the World Wide Web. The differences between the Web graph and other networks ensure that classical random graph models are of no use. Researchers have proposed a variety of random graphs that have some Web-like behaviour but are not sufficiently sophisticated to model it. Dr. Reed intends to develop models that are closer approximations of the Web. This will involve studying current models to understand how they behave and studying the Web to understand its behaviour.