A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs (Q1962057)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs |
scientific article |
Statements
A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs (English)
0 references
19 July 2000
0 references
A graph \(G\) is a distance hereditary graph if for each pair of vertices \(v,w\in V_G\), their distance in all induced subgraphs of \(G\) that contain \(v\) and \(w\) is the same. The minimum fill-in problem is to find a chordal supergraph of a given graph with the minimum number of edges. The treewidth problem is to find a chordal supergraph of a given graph with the minimum maximum clique size, or alternatively, to find a tree decomposition of minimum width. This paper is one of a collection of papers that address the complexity of the minimum fill-in or treewidth problem for special graphs. It is shown that both problems can be solved in linear time when the input graph is distance hereditary. As a first step in the algorithms, a representation of the graph by a fragment tree is made.
0 references
distance hereditary graph
0 references
minimum fill-in problem
0 references
treewidth
0 references
clique
0 references
tree decomposition
0 references
complexity
0 references
algorithms
0 references