Minimum fill-in for chordal bipartite graphs
Ajj Ton Kloks · TU/e Research Portal · 1993
Chordal bipartite graph are exactly those bipartite graph in which every cycle of length at least six has a chord. The MINIMUM FILL-IN problem is the problem of finding a chordal embedding of the graph with a minimum number of edges. We present a polynomial time algorithm for the exact computation of the minimum fill-in for all chordal bipartite graphs.