# zbMATH — the first resource for mathematics

Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree. (English) Zbl 1155.68088
Summary: 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.

##### MSC:
 68W10 Parallel algorithms in computer science
Full Text:
##### References:
  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  A. Berry, Désarticulation d’un graphe, Ph.D. Dissertation, LIRMM, Montpellier, December 1998  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  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)  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  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  Blair, J.R.S.; Peyton, B.W., An introduction to chordal graphs and clique trees, (), 1-30 · Zbl 0803.68081  Cole, R., Parallel merge sort, SIAM J. comput., 17, 770-785, (1988) · Zbl 0651.68077  Dahlhaus, E., Minimal elimination ordering inside a given chordal graph, (), 132-143 · Zbl 0886.05103  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  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  Dirac, G.A., On rigid circuit graphs, Anh. math. sem. univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703  Fulkerson, D.R.; Gross, O.A., Incidence matrices and interval graphs, Pacific J. math., 15, 835-855, (1965) · Zbl 0132.21001  George, J.A.; Liu, J.W.H., The evolution of the minimum degree ordering algorithm, SIAM rev., 31, 1-19, (1989) · Zbl 0671.65024  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.  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  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  Markowitz, H.M., The elimination form of the inverse and its application to linear programming, Manag. sci., 3, 255-269, (1957) · Zbl 0995.90592  Matrix Market. Web site: http://math.nist.gov/MatrixMarket/  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  Parra, A.; Scheffler, P., Characterizations and algorithmic applications of chordal graph embeddings, Discrete appl. math., 79, 171-188, (1997) · Zbl 0887.05044  Parter, S., The use of linear graphs in Gauss elimination, SIAM review, 3, 119-130, (1961) · Zbl 0102.11302  Peyton, B., Minimal orderings revisited, SIAM J. matrix anal. appl., 23, 271-294, (2001) · Zbl 1044.65035  Rose, D.J., Triangulated graphs and the elimination process, J. math. anal. appl., 32, 597-609, (1970) · Zbl 0216.02602  Rose, D.J., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, (), 183-217  Shiloach, Y.; Vishkin, U., An $$O(\log n)$$ parallel connectivity algorithm, J. algorithms, 3, 57-67, (1982) · Zbl 0494.68070  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  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  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  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.