Practical parallel algorithms for chordal graphs

Author

Eric Stewart Kirsch

Date of Award

5-1989

Degree Type

Thesis

Degree Name

Master of Science

Major

Computer Science

Major Professor

Jean Blair

Committee Members

David W. Straight. Dunigan

Abstract

Given a chordal graph, parallel solutions are given for finding the set of maximal cliques, a perfect elimination ordering and a minimum coloring. The solutions to these problems have a variety of applications. While other parallel solutions to these problems exist, this paper presents algorithms that use resources more efficiently and involve less total computation and so have a faster running time on a fixed number of processors. Questions of processor grain size, communication costs, algorithm costs and possible pipelining benefits are also discussed.

Recommended Citation

Kirsch, Eric Stewart, "Practical parallel algorithms for chordal graphs. " Master's Thesis, University of Tennessee, 1989.
https://trace.tennessee.edu/utk_gradthes/12989