Some practical experiences of hard graph problems

Presented by: Dr Keith Briggs, BT.

Abstract: Several of the most basic computations in graph theory, such as determining the chromatic number or clique number, are proven to be NP-complete. This means that it unlikely that any algorithm exists which runs in time which is a polynomial function of the number of nodes, and indeed experience shows that the time typically grows exponentially. Faced with this situation, we have two options: (1) use a heuristic, which is probably fast but may give the wrong answer; or, (2) use an exact algorithm, and try to make it as fast as possible by clever coding, efficient memory management etc. As computers get faster, option (2) becomes more feasible. Although the theory of the required algorithms is well developed and presented in many places, little practical experience gets reported; therefore, my aim in this talk is to give a summary of my own experiences, with an emphasis on the practicality of the various algorithms. One useful outcome is that it is possible to determine by simulation the accuracy for small graphs of some results only known to be true for infinitely large graphs.

1.15 p.m. 12th June 2006 

Venue: BICS seminar room. (1W 3.6, University of Bath).

ALL WELCOME