×

zbMATH — the first resource for mathematics

A vertex incremental approach for maintaining chordality. (English) Zbl 1087.05054
Summary: For a chordal graph \(G=(V,E)\), we study the problem of whether a new vertex \(u \notin V\) and a given set of edges between \(u\) and vertices in \(V\) can be added to \(G\) so that the resulting graph remains chordal. We show how to resolve this efficiently, and at the same time, if the answer is no, specify a maximal subset of the proposed edges that can be added along with \(u\), or conversely, a minimal set of extra edges that can be added in addition to the given set, so that the resulting graph is chordal. In order to do this, we give a new characterization of chordal graphs and, for each potential new edge \(uv\), a characterization of the set of edges incident to \(u\) that also must be added to \(G\) along with \(uv\). We propose a data structure that can compute and add each such set in O\((n)\) time. Based on these results, we present an algorithm that computes both a minimal triangulation and a maximal chordal subgraph of an arbitrary input graph in O\((nm)\) time, using a totally new vertex incremental approach. In contrast to previous algorithms, our process is on-line in that each new vertex is added without reconsidering any choice made at previous steps, and without requiring any knowledge of the vertices that might be added subsequently.

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX Cite
Full Text: DOI
References:
[1] Arikati, S.; Rangan, P., An efficient algorithm for finding a two-pair, and its applications, Discrete appl. math., 31, 71-74, (1991) · Zbl 0748.05085
[2] Balas, E., A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring, Discrete appl. math., 15, 123-134, (1986) · Zbl 0633.05039
[3] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database systems, J. assoc. comput. Mach., 30, 479-513, (1983) · Zbl 0624.68087
[4] A. Berry, A wide-range efficient algorithm for minimal triangulation, in: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 1999. · Zbl 0938.68074
[5] Berry, A.; Blair, J.; Heggernes, P.; Peyton, B., Maximum cardinality search for computing minimal triangulations of graphs, Algorithmica, 39, 4, 287-298, (2004) · Zbl 1090.68080
[6] A. Berry, J.-P. Bordat, Triangulated and weakly triangulated graphs: simpliciality in vertices and edges, 6th International Conference on Graph Theory (ICGT 2000), 2000 (Communication).
[7] Berry, A.; Bordat, J.-P.; Heggernes, P., Recognizing weakly triangulated graphs by edge separability, Nordic J. comput., 7, 164-177, (2000) · Zbl 0972.68126
[8] Berry, A.; Bordat, J.-P.; Heggernes, P.; Simonet, G.; Villanger, Y., A wide-range algorithm for minimal triangulation from an arbitrary ordering, J. algorithms, 58, 1, 33-66, (2006) · Zbl 1093.68137
[9] A. Berry, A. Sigayret, Obtaining and maintaining polynomial-size concept lattices, in: Proceedings of FCAKDD, (ECAI 2002), 2002, pp. 3-6.
[10] A. Berry, A. Sigayret, C. Sinoquet, Maximal sub-triangulation as improving phylogenetic data, Technical Report RR-02-02, LIMOS, Clermont-Ferrand, France, 2002. · Zbl 1096.68682
[11] Blair, J.R.S.; Heggernes, P.; Telle, J.A., A practical algorithm for making filled graphs minimal, Theoret. comput. sci., 250, 125-141, (2001) · Zbl 0952.68104
[12] Blair, J.R.S.; Peyton, B.W., An introduction to chordal graphs and clique trees, (), 1-30 · Zbl 0803.68081
[13] Bodlaender, H.L.; Möhring, R.H., The pathwidth and treewidth of cographs, SIAM J. discrete math., 6, 2, 181-188, (1993) · Zbl 0773.05091
[14] Buneman, P., A characterization of rigid circuit graphs, Discrete math., 9, 205-212, (1974) · Zbl 0288.05128
[15] Coleman, T.F., A chordal preconditioner for large-scale optimization, Appl. math., 40, 265-287, (1988) · Zbl 0685.90085
[16] Dahlhaus, E., Minimal elimination ordering inside a given chordal graph, (), 132-143 · Zbl 0886.05103
[17] Dearing, P.M.; Shier, D.R.; Warner, D.D., Maximal chordal subgraphs, Discrete appl. math., 20, 181-190, (1988) · Zbl 0664.05032
[18] A. Deshpande, M. Garofalakis, M.I. Jordan, Efficient stepwise selection in decomposable models, in: Proceedings of UAI, 2001, pp. 128-135.
[19] Dirac, G.A., On rigid circuit graphs, Abh. math. sem. univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703
[20] Erdös, P.; Laskar, R., On maximum chordal subgraph, Congr. numer., 39, 367-373, (1983) · Zbl 0534.05037
[21] Fulkerson, D.R.; Gross, O.A., Incidence matrices and interval graphs, Pacific J. math., 15, 835-855, (1965) · Zbl 0132.21001
[22] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. combin. theory ser. B, 16, 47-56, (1964) · Zbl 0266.05101
[23] Hayward, R., Generating weakly triangulated graphs, J. graph theory, 21, 67-70, (1996) · Zbl 0837.05075
[24] Hayward, R.; Hoàng, C.; Maffray, F., Optimizing weakly triangulated graphs, Graphs combin., 5, 339-349, (1989) · Zbl 0679.68082
[25] R. Hayward, J. Spinrad, R. Sritharan, Weakly chordal graph algorithms via handles, in: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, 2000. · Zbl 0956.68104
[26] Heggernes, P.; Villanger, Y., Efficient implementation of a minimal triangulation algorithm, (), 550-561 · Zbl 1019.68809
[27] Ho, C.-W.; Lee, R.C.T., Counting clique trees and computing perfect elimination schemes in parallel, Inform. process. lett., 31, 61-68, (1989) · Zbl 0685.68050
[28] L. Ibarra, Fully dynamic algorithms for chordal graphs, in: Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 1999. · Zbl 0929.68087
[29] M. Lundquist, Zero patterns chordal graphs and matrix completions, Ph.D. Thesis, Clemson University, USA, 1990.
[30] Natanzon, A.; Shamir, R.; Sharan, R., Complexity classification of some edge modification problems, Discrete appl. math., 113, 109-128, (2001) · Zbl 0982.68104
[31] Rose, D.J., A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, (), 183-217
[32] 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
[33] Spinrad, J.; Sritharan, R., Algorithms for weakly triangulated graphs, Discrete appl. math., 59, 181-191, (1995) · Zbl 0827.68084
[34] J. Walter, Representations of rigid cycle graphs, Ph.D. Thesis, Wayne State University, USA, 1972.
[35] Xue, J., Edge-maximal triangulated subgraphs and heuristics for the maximum clique problem, Networks, 24, 109-120, (1994) · Zbl 0791.90065
[36] Yannakakis, M., Computing the minimum fill-in is NP-complete, SIAM J. algebraic 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.