A generalization of chordal graphs and the maximum clique problem

DOI10.1016/S0020-0190(97)00044-6zbMath1336.05110OpenAlexW2054972273MaRDI QIDQ287036

Assef Chmeiss, Philippe Jégou

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00044-6

zbMATH Keywords

computational complexitycombinatorial problemschordal graphsmaximum clique problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ Root bundles and towards exact matter spectra of F-theory MSSMs

Cites Work

• Weakly triangulated graphs
• Incidence matrices and interval graphs
• Triangulated graphs and the elimination process
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Finding a Maximum Clique in an Arbitrary Graph
• Algorithmic Aspects of Vertex Elimination on Graphs
• Edge‐maximal triangulated subgraphs and heuristics for the maximum clique problem
• Reducibility among Combinatorial Problems
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: A generalization of chordal graphs and the maximum clique problem