Efficient parallel algorithms on chordal graphs with a sparse tree representation

Author

Dahlhaus, Elias

Author_Institution

Dept. of Comput. Sci., Sydney Univ., NSW, Australia

Volume

2

fYear

1994

fDate

4-7 Jan. 1994

Firstpage

150

Lastpage

158

Abstract

Chordal graphs are nothing else than intersection graphs of subtrees of a tree. We present optimal and almost-optimal algorithms for certain graph problems if the input graph is given by a collection of subtrees of a tree and the subtrees are given by their leaves. This generalizes results of Olariu, Schwing and Zhang (1992), Kim (1989) and Chen (1992) concerning the parallel complexity of problems on interval graphs provided the interval structure is given. In particular, we consider the problems to find a breadth-first search tree, to find a depth-first search tree, to find a minimum covering of the vertices by cliques, and to find a minimum coloring.<>

Keywords

computational complexity; graph colouring; parallel algorithms; search problems; trees (mathematics); breadth-first search tree; chordal graphs; cliques; depth-first search tree; efficient parallel algorithms; intersection graphs; interval graphs; interval structure; leaves; minimum coloring; minimum covering; optimal algorithms; parallel complexity; sparse tree representation; subtrees; vertices;

fLanguage

English

Publisher

ieee

Conference_Titel

System Sciences, 1994. Proceedings of the Twenty-Seventh Hawaii International Conference on

Conference_Location

Wailea, HI, USA

Print_ISBN

0-8186-5090-7

Type

conf

DOI

10.1109/HICSS.1994.323270

Filename

323270