Abstract In this paper, we present a polynomial algorithm that finds an edge‐maximal triangulated subgraph of an arbitrary graph. Then, we use this algorithm as a heuristic for the maximum (weight) clique problem. Finally, a local search routine is incorporated into our heuristic. Computational results comparing our algorithm with two existing edge‐maximal triangulated subgraph algorithms in the literature show that the subgraphs found by our algorithm tend to contain more edges as well as a better clique of the original graph. Computational results comparing our heuristic with other heuristics, including an efficient randomized heuristic, also show the promise of our heuristic. © 1994 by John Wiley & Sons, Inc.

Previous article Addendum: Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary GraphsEgon Balas and Jue XueEgon Balas and Jue Xuehttps://doi.org/10.1137/0221058PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout"Addendum: Minimum Weighted Coloring of Triangulated Graphs, with Application to Maximum Weight Vertex Packing and Clique Finding in Arbitrary Graphs." SIAM Journal on Computing, 21(5), p. 1000[1] Egon Balas and , Jue Xue, Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs, SIAM J. Comput., 20 (1991), 209–221 10.1137/0220012 92h:68069 0722.68086 LinkISIGoogle Scholar[2] Egon Balas, A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring, Discrete Appl. Math., 15 (1986), 123–134 10.1016/0166-218X(86)90036-3 88e:05037 0633.05039 CrossrefISIGoogle Scholar[3] J. Xue, Ph.D. Thesis, Fast Algorithms for Vertex Packing and Related Problems, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1991 Google Scholar Previous article FiguresRelatedReferencesCited byDetails Clique, Independent Set, and Vertex Cover12 October 2021 Cross Ref Edge-maximal triangulated subgraphs and heuristics for the maximum clique problemNetworks, Vol. 24, No. 2 Cross Ref Volume 21, Issue 5| 1992SIAM Journal on Computing History Submitted:28 July 1992Accepted:28 July 1992Published online:13 July 2006 InformationCopyright © 1992 Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/0221058Article page range:pp. 1000-1000ISSN (print):0097-5397ISSN (online):1095-7111Publisher:Society for Industrial and Applied Mathematics

Efficient algorithms are known for finding a maximum weight stable set, a minimum weighted clique covering, and a maximum weight clique of a vertex-weighted triangulated graph. However, there is no comparably efficient algorithm in the literature for finding a minimum weighted vertex coloring of such a graph. This paper gives an $O(|V|^2 )$ procedure for the problem (Algorithm 1). It then extends the procedure to the problem of finding in an arbitrary graph $G = (V,E)$ a maximal induced subgraph $G(W)$ color-equivalent (as defined in § 3) to a maximal triangulated subgraph $G(T)$ (Algorithm 2). Finally, it uses this latter algorithm as the main ingredient of a branch-and-bound procedure for the maximum weight clique problem in an arbitrary graph. Computational experience is presented on arbitrary random graphs with up to 2,000 vertices.