Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree.

*(English)*Zbl 1155.68088Summary: Elimination Game is a well-known algorithm that simulates Gaussian elimination of matrices on graphs, and it computes a triangulation of the input graph. The number of fill edges in the computed triangulation is highly dependent on the order in which Elimination Game processes the vertices, and in general the produced triangulations are neither minimum nor minimal. In order to obtain a triangulation which is close to minimum, the Minimum Degree heuristic is widely used in practice, but until now little was known on the theoretical mechanisms involved.

In this paper we show some interesting properties of Elimination Game; in particular that it is able to compute a partial minimal triangulation of the input graph regardless of the order in which the vertices are processed. This results in a new algorithm to compute minimal triangulations that are sandwiched between the input graph and the triangulation resulting from Elimination Game. One of the strengths of the new approach is that it is easily parallelizable, and thus we are able to present the first parallel algorithm to compute such sandwiched minimal triangulations. In addition, the insight that we gain through Elimination Game is used to partly explain the good behavior of the Minimum Degree algorithm. We also give a new algorithm for producing minimal triangulations that is able to use the minimum degree idea to a wider extent.

In this paper we show some interesting properties of Elimination Game; in particular that it is able to compute a partial minimal triangulation of the input graph regardless of the order in which the vertices are processed. This results in a new algorithm to compute minimal triangulations that are sandwiched between the input graph and the triangulation resulting from Elimination Game. One of the strengths of the new approach is that it is easily parallelizable, and thus we are able to present the first parallel algorithm to compute such sandwiched minimal triangulations. In addition, the insight that we gain through Elimination Game is used to partly explain the good behavior of the Minimum Degree algorithm. We also give a new algorithm for producing minimal triangulations that is able to use the minimum degree idea to a wider extent.

##### MSC:

68W10 | Parallel algorithms in computer science |

PDF
BibTeX
XML
Cite

\textit{A. Berry} et al., Theor. Comput. Sci. 409, No. 3, 601--616 (2008; Zbl 1155.68088)

Full Text:
DOI

##### References:

[1] | Amestoy, P.; Davis, T.A.; Duff, I.S., An approximate minimum degree ordering algorithm, SIAM J. matrix anal. appl., 17, 886-905, (1996) · Zbl 0861.65021 |

[2] | A. Berry, Désarticulation d’un graphe, Ph.D. Dissertation, LIRMM, Montpellier, December 1998 |

[3] | Berry, A.; Blair, J.R.S.; Heggernes, P.; Peyton, B.W., Maximum cardinality search for computing minimal triangulations of graphs, Algorithmica, 39, 4, 287-298, (2004) · Zbl 1090.68080 |

[4] | Berry, A.; Bordat, J.-P.; Heggernes, P.; Simonet, G.; Villanger, Y., A wide-range algorithm for minimal triangulation from an arbitrary ordering, J. algorithms, 57, 2, (2005) |

[5] | A. Berry, P. Heggernes, G. Simonet, The minimum degree heuristic and the minimal triangulation process, in: Proceedings WG 2003 — 29th Workshop on Graph Theoretic Concepts in Computer Science, June 2003, in: Lecture Notes in Computer Science, vol. 2880, pp. 58-70 · Zbl 1255.05186 |

[6] | Blair, J.R.S.; Heggernes, P.; Telle, J.A., A practical algorithm for making filled graphs minimal, Theoret. comput. sci., 250, 124-141, (2001) · Zbl 0952.68104 |

[7] | Blair, J.R.S.; Peyton, B.W., An introduction to chordal graphs and clique trees, (), 1-30 · Zbl 0803.68081 |

[8] | Cole, R., Parallel merge sort, SIAM J. comput., 17, 770-785, (1988) · Zbl 0651.68077 |

[9] | Dahlhaus, E., Minimal elimination ordering inside a given chordal graph, (), 132-143 · Zbl 0886.05103 |

[10] | Dahlhaus, E., Parallel algorithms for hierarchical clustering and applications to split decomposition and parity graph recognition, J. algorithms, 36, 205-240, (2000) · Zbl 0961.68152 |

[11] | Dahlhaus, E.; Karpinski, M., An efficient parallel algorithm for the minimal elimination ordering of an arbitrary graph, Theoret. comput. sci., 134, 2, 493-528, (1994) · Zbl 0938.68958 |

[12] | Dirac, G.A., On rigid circuit graphs, Anh. math. sem. univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703 |

[13] | Fulkerson, D.R.; Gross, O.A., Incidence matrices and interval graphs, Pacific J. math., 15, 835-855, (1965) · Zbl 0132.21001 |

[14] | George, J.A.; Liu, J.W.H., The evolution of the minimum degree ordering algorithm, SIAM rev., 31, 1-19, (1989) · Zbl 0671.65024 |

[15] | P. Heggernes, S. Eisenstat, G. Kumfert, A. Pothen, The computational complexity of the minimum degree algorithm, in: Proceedings of 14th Norwegian Computer Science Conference, NIK 2001, University of Tromsø, Norway. Also available as ICASE Report 2001-42, NASA/CR-2001-211421, NASA Langley Research Center, USA. |

[16] | Kloks, T.; Kratsch, D.; Spinrad, J., On treewidth and minimum fill-in of asteroidal triple-free graphs, Theoret. comput. sci., 175, 309-335, (1997) · Zbl 0903.68139 |

[17] | Lekkerkerker, C.G.; Boland, J.Ch., Representation of a finite graph by a set of intervals on the real line, Fund. math., 51, 45-64, (1962) · Zbl 0105.17501 |

[18] | Markowitz, H.M., The elimination form of the inverse and its application to linear programming, Manag. sci., 3, 255-269, (1957) · Zbl 0995.90592 |

[19] | Matrix Market. Web site: http://math.nist.gov/MatrixMarket/ |

[20] | Ohtsuki, T.; Cheung, L.K.; Fujisawa, T., Minimal triangulation of a graph and optimal pivoting order in a sparse matrix, J. math. anal. appl., 54, 622-633, (1976) · Zbl 0371.65006 |

[21] | Parra, A.; Scheffler, P., Characterizations and algorithmic applications of chordal graph embeddings, Discrete appl. math., 79, 171-188, (1997) · Zbl 0887.05044 |

[22] | Parter, S., The use of linear graphs in Gauss elimination, SIAM review, 3, 119-130, (1961) · Zbl 0102.11302 |

[23] | Peyton, B., Minimal orderings revisited, SIAM J. matrix anal. appl., 23, 271-294, (2001) · Zbl 1044.65035 |

[24] | Rose, D.J., Triangulated graphs and the elimination process, J. math. anal. appl., 32, 597-609, (1970) · Zbl 0216.02602 |

[25] | Rose, D.J., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, (), 183-217 |

[26] | Shiloach, Y.; Vishkin, U., An \(O(\log n)\) parallel connectivity algorithm, J. algorithms, 3, 57-67, (1982) · Zbl 0494.68070 |

[27] | Rose, D.J.; Tarjan, R.E.; Lueker, G.S., Algorithmic aspects of vertex elimination on graphs, SIAM J. comput., 5, 266-283, (1976) · Zbl 0353.65019 |

[28] | Tarjan, R.E.; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. comput., 13, 566-579, (1984) · Zbl 0545.68062 |

[29] | W.F. Tinney, J.W. Walker, Direct solutions of sparse network equations by optimally ordered triangular factorization, in: Proceedings of the IEEE, vol. 55, 1967, pp. 1801-1809 |

[30] | Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. algebra discrete methods, 2, 77-79, (1981) · Zbl 0496.68033 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.