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

doi:10.1016/S0166-218X(99)00146-8

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

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

24 Citations (Scopus)

313 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 language	English
Pages (from-to)	367-400
Number of pages	34
Journal	Discrete applied mathematics
Volume	99
Issue number	1-3
DOIs	https://doi.org/10.1016/S0166-218X(99)00146-8
Publication status	Published - 2000

Keywords

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

Access to Document

10.1016/S0166-218X(99)00146-8Licence: Other

Broersma00linearFinal published version, 263 KBLicence: Other

Cite this

@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",

}

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

SN - 0166-218X

VL - 99

SP - 367

EP - 400

JO - Discrete applied mathematics

JF - Discrete applied mathematics

IS - 1-3

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this