A generalization of chordal graphs and the maximum clique problem

DOI10.1016/S0020-0190(97)00044-6zbMATH Open1336.05110OpenAlexW2054972273MaRDI QIDQ287036FDOQ287036

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

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

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)

Cites Work

• Reducibility among combinatorial problems
• 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
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Weakly triangulated graphs

Cited In (11)

• Optimal‐size clique transversals in chordal graphs
• Root bundles and towards exact matter spectra of F-theory MSSMs
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Recognizing \(k\)-clique extendible orderings
• Fixed interval scheduling: models, applications, computational complexity and algorithms
• 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)