Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs
Department of Computer and Communication Engineering, Ming Chuan University, 5 De Ming Road, Guishan District, Taoyuan City 333, Taiwan
Algorithms 2021, 14(1), 22; https://0-doi-org.brum.beds.ac.uk/10.3390/a14010022
Received: 9 December 2020 / Revised: 4 January 2021 / Accepted: 11 January 2021 / Published: 13 January 2021
(This article belongs to the Special Issue Graph Algorithms and Applications)
This paper studies the maximum-clique independence problem and some variations of the clique transversal problem such as the -clique, maximum-clique, minus clique, signed clique, and k-fold clique transversal problems from algorithmic aspects for k-trees, suns, planar graphs, doubly chordal graphs, clique perfect graphs, total graphs, split graphs, line graphs, and dually chordal graphs. We give equations to compute the -clique, minus clique, signed clique, and k-fold clique transversal numbers for suns, and show that the -clique transversal problem is polynomial-time solvable for graphs whose clique transversal numbers equal their clique independence numbers. We also show the relationship between the signed and generalization clique problems and present NP-completeness results for the considered problems on k-trees with unbounded k, planar graphs, doubly chordal graphs, total graphs, split graphs, line graphs, and dually chordal graphs.
View Full-Text
Keywords:
clique independent set; clique transversal number; signed clique transversal function; minus clique transversal function; k-fold clique transversal set
▼
Show Figures
This is an open access article distributed under the Creative Commons Attribution License which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited
MDPI and ACS Style
Lee, C.-M. Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs. Algorithms 2021, 14, 22. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010022
AMA Style
Lee C-M. Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs. Algorithms. 2021; 14(1):22. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010022
Chicago/Turabian StyleLee, Chuan-Min. 2021. "Algorithmic Aspects of Some Variations of Clique Transversal and Clique Independent Sets on Graphs" Algorithms 14, no. 1: 22. https://0-doi-org.brum.beds.ac.uk/10.3390/a14010022
Find Other Styles
Note that from the first issue of 2016, MDPI journals use article numbers instead of page numbers. See further details here.
Search more from Scilit