A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs (Q1962057): Difference between revisions

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.