Detecting strong cliques
- Hujdurovic, Ademir University of Primorska, Slovenia
- Milanic, Martin University of Primorska, Slovenia
- Ries, Bernard University of Fribourg, Switzerland
-
2019
Published in:
- Discrete Mathematics. - 2019, vol. 342, no. 9, p. 2738-2750
English
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.
- Faculty
- Faculté des sciences économiques et sociales et du management
- Department
- Département d'informatique
- Language
-
- English
- Classification
- Computer science and technology
- License
- License undefined
- Identifiers
-
- RERO DOC 326930
- DOI 10.1016/j.disc.2019.06.010
- Persistent URL
- https://folia.unifr.ch/unifr/documents/307860
Statistics
Document views: 41
File downloads:
- strongcliquesrero.pdf: 163