### Abstract

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.

Original language | English |
---|---|

Pages (from-to) | 367-400 |

Number of pages | 34 |

Journal | Discrete applied mathematics |

Volume | 99 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 2000 |

### Keywords

- Chordal graphs
- Fragment tree
- Minimum fill-in
- Distance hereditary graphs
- Tree representation
- Treewidth
- Linear time algorithm

## Fingerprint Dive into the research topics of 'A linear time algorithm for minimum fill-in and treewidth for distance heredity graphs'. Together they form a unique fingerprint.

## Cite this

Broersma, H. J., Dahlhaus, E., Kloks, A. J. J., & Kloks, T. (2000). A linear time algorithm for minimum fill-in and treewidth for distance heredity graphs.

*Discrete applied mathematics*,*99*(1-3), 367-400. https://doi.org/10.1016/S0166-218X(99)00146-8