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

19 Citations (Scopus)
4 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

Fingerprint

Distance Graph
Treewidth
Linear-time Algorithm
Distance-hereditary Graphs
Clique number
Induced Subgraph
Graph in graph theory
Linear Time

Keywords

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

Cite this

Broersma, Haitze J. ; Dahlhaus, E. ; Kloks, A.J.J. ; Kloks, T. / A linear time algorithm for minimum fill-in and treewidth for distance heredity graphs. In: Discrete applied mathematics. 2000 ; Vol. 99, No. 1-3. pp. 367-400.
@article{e271e232ee464bc888a1f6aab5f04b3a,
title = "A linear time algorithm for minimum fill-in and treewidth for distance heredity graphs",
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.",
keywords = "Chordal graphs, Fragment tree, Minimum fill-in, Distance hereditary graphs, Tree representation, Treewidth, Linear time algorithm",
author = "Broersma, {Haitze J.} and E. Dahlhaus and A.J.J. Kloks and T. Kloks",
year = "2000",
doi = "10.1016/S0166-218X(99)00146-8",
language = "English",
volume = "99",
pages = "367--400",
journal = "Discrete applied mathematics",
issn = "0166-218X",
publisher = "Elsevier",
number = "1-3",

}

A linear time algorithm for minimum fill-in and treewidth for distance heredity graphs. / Broersma, Haitze J.; Dahlhaus, E.; Kloks, A.J.J.; Kloks, T.

In: Discrete applied mathematics, Vol. 99, No. 1-3, 2000, p. 367-400.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Broersma, Haitze J.

AU - Dahlhaus, E.

AU - Kloks, A.J.J.

AU - Kloks, T.

PY - 2000

Y1 - 2000

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

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

KW - Chordal graphs

KW - Fragment tree

KW - Minimum fill-in

KW - Distance hereditary graphs

KW - Tree representation

KW - Treewidth

KW - Linear time algorithm

U2 - 10.1016/S0166-218X(99)00146-8

DO - 10.1016/S0166-218X(99)00146-8

M3 - Article

VL - 99

SP - 367

EP - 400

JO - Discrete applied mathematics

JF - Discrete applied mathematics

SN - 0166-218X

IS - 1-3

ER -