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

Haitze J. Broersma, E. Dahlhaus, A.J.J. Kloks, T. Kloks

Research output: Contribution to journalArticleAcademicpeer-review

20 Citations (Scopus)
21 Downloads (Pure)

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 languageEnglish
Pages (from-to)367-400
Number of pages34
JournalDiscrete applied mathematics
Volume99
Issue number1-3
DOIs
Publication statusPublished - 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