| Article ID: | iaor20012913 |
| Country: | Netherlands |
| Volume: | 99 |
| Issue: | 1/3 |
| Start Page Number: | 367 |
| End Page Number: | 400 |
| Publication Date: | Feb 2000 |
| Journal: | Discrete Applied Mathematics |
| Authors: | Broersma H.J., Dahlhaus E., Kloks T. |
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.