# A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs

Broersma, H.J.
and
Dahlhaus, E.
and
Kloks, T.
(2000)
*A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs.*
Discrete Applied Mathematics, 99
(1-3).
pp. 367-400.
ISSN 0166-218X

PDF
Restricted to UT campus only : Request a copy 269kB |

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. |

Item Type: | Article |

Copyright: | © 2000 Elsevier |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/74245 |

Official URL: | http://dx.doi.org/10.1016/S0166-218X(99)00146-8 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 140630