# 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

19 Citations (Scopus)

### 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 367-400 34 Discrete applied mathematics 99 1-3 https://doi.org/10.1016/S0166-218X(99)00146-8 Published - 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.

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 -