TREEWIDTH OF CHORDAL BIPARTITE GRAPHS

Chordal bipartite graphs are exactly those bipartite graphs in which e very cycle of length at least six has a chord. The treewidth of a grap h G is the smallest maximum cliquesize among all chordal supergraphs o f G decreased by one. We present a polynomial time algorithm for the e xact computation of the treewidth of all chordal bipartite graphs. The algorithm can be implemented to run in time O(m(alpha)) which is the time needed to multiply two m X m matrices, where m is the number of e dges of the graph. (C) 1995 Academic Press, Inc.