A generalization of chordal graphs and the maximum clique problem

DOI10.1016/S0020-0190(97)00044-6MaRDI QIDQ287036zbMATH OpenOpenAlexFDO

Authors 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 complexitychordal graphscombinatorial problemsmaximum clique problem

Mathematics Subject Classification ID

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

Recommendations

• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• On the clique-transversal number of chordal graphs
• Clique tree generalization and new subclasses of chordal graphs
• On generalized split graphs
• scientific article; zbMATH DE number 4134090

Cites work

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

Cited in

(11)

• Optimal‐size clique transversals in chordal graphs
• Root bundles and towards exact matter spectra of F-theory MSSMs
• scientific article; zbMATH DE number 5521219 (Why is no real title available?)
• scientific article; zbMATH DE number 4134082 (Why is no real title available?)
• A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph
• A min-max property of chordal bipartite graphs with applications
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• Recognizing \(k\)-clique extendible orderings
• Linear degree extractors and the inapproximability of max clique and chromatic number
• On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem
• On the maxima of Motzkin-Straus programs and cliques of graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q287036)