Next Article in Journal
Simheuristics Approaches for Efficient Decision-Making Support in Materials Trading Networks
Next Article in Special Issue
A Quasi-Hole Detection Algorithm for Recognizing k-Distance-Hereditary Graphs, with k < 2
Previous Article in Journal
Dynamic Shortest Paths Methods for the Time-Dependent TSP
Previous Article in Special Issue
Efficient Approaches to the Mixture Distance Problem
Open AccessArticle

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
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 {k}-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 {k}-clique, minus clique, signed clique, and k-fold clique transversal numbers for suns, and show that the {k}-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 clique independent set; clique transversal number; signed clique transversal function; minus clique transversal function; k-fold clique transversal set
Show Figures

Figure 1

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 Style

Lee, 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.

Article Access Map by Country/Region

1
Search more from Scilit
 
Search
Back to TopTop