A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs Original Research Article

A graph is distance hereditary if it preserves distances in all its connected induced subgraphs. The MINIMUM FILL-IN problem is the problem of finding a chordal supergraph with the smallest possible number of edges. The TREEWIDTH problem is the problem of finding a chordal embedding of the graph with the smallest possible clique number. In this paper we show that both problems are solvable in linear time for distance hereditary graphs.