Detecting strong cliques
From MaRDI portal
Publication:2312812
Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)
Abstract: A strong clique in a graph is a clique intersecting every maximal independent set. We study the computational complexity of six algorithmic decision problems related to strong cliques in graphs and almost completely determine their complexity in the classes of chordal graphs, weakly chordal graphs, line graphs and their complements, and graphs of maximum degree at most three. Our results rely on connections with matchings and relate to several graph properties studied in the literature, including well-covered graphs, localizable graphs, and general partition graphs.
Recommendations
Cites work
- scientific article; zbMATH DE number 434906 (Why is no real title available?)
- scientific article; zbMATH DE number 3889565 (Why is no real title available?)
- scientific article; zbMATH DE number 3878985 (Why is no real title available?)
- scientific article; zbMATH DE number 1286748 (Why is no real title available?)
- scientific article; zbMATH DE number 1076150 (Why is no real title available?)
- scientific article; zbMATH DE number 205349 (Why is no real title available?)
- A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
- A characterization and hereditary properties for partition graphs
- A characterization of almost CIS graphs
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
- Complexity results for well‐covered graphs
- Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
- Equistable graphs, general partition graphs, triangle graphs, and graph products
- Equistable simplicial, very well-covered, and line graphs
- Equistarable bipartite graphs
- Equistarable graphs and counterexamples to three conjectures on equistable graphs
- Generalizations of Grillet's theorem on maximal stable sets and maximal cliques in graphs
- Graph-Theoretic Concepts in Computer Science
- Graphs vertex-partitionable into strong cliques
- Local Structure When All Maximal Independent Sets Have Equal Weight
- Matching theory
- Maximum matching and a polyhedron with 0,1-vertices
- Modeling k-coteries by well-covered graphs
- NP-completeness of edge-colouring some restricted graphs
- Normal hypergraphs and the perfect graph conjecture
- On CIS circulants
- On a conjecture of Meyniel
- On equistable, split, CIS, and related classes of graphs
- On exact blockers and anti-blockers, \(\varDelta \)-conjecture, and related problems
- On split and almost CIS-graphs
- On the Complexity of Timetable and Multicommodity Flow Problems
- On the perfect graph conjecture
- Paths, Trees, and Flowers
- Some covering concepts in graphs
- Stochastic graphs and strongly perfect graphs - a survey
- Strong cliques and equistability of EPT graphs
- Vertex-transitive CIS graphs
- WELL-COVERED GRAPHS: A SURVEY
- Well covered simplicial, chordal, and circular arc graphs
Cited in
(5)
This page was built for publication: Detecting strong cliques
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2312812)
