A wide-range efficient algorithm for minimal triangulation
Anne Berry · 1999
Traditionally, efficient algorithms for computing a minimal triangulation of a graph (i.e. embedding a graph into a triangulated graph by adding an inclusion-minimal set of edges) required first computing a special ordering on the vertices of the graph, called a minimal ordering. We give a new algorithm which efficiently computes a minimal triangulation using an arbitrary ordering on the vertices. 1 Introduction. Computing a minimal triangulation consists in embedding a given graph into a triangulated graph by adding a set of edges (called a fill). If the set of edges added is inclusion-minimal, the fill is said to be minimal, and the corresponding triangulated graph is called a minimal triangulation. Finding a fill that is minimum is NP-complete ([10]). Given a graph G and any ordering ff on its vertices, an associated fill can be computed by repeatedly choosing the next vertex x in order ff, adding the edges necessary to make the neighborhood of x into a clique (i.e. by making x si...