The algorithmic complexity of the minus clique-transversal problem

DOI10.1016/j.amc.2006.12.027zbMath1125.05076OpenAlexW1971095627MaRDI QIDQ2383654

Guangjun Xu, Erfang Shan, Cheng, T. C. Edwin, Li-ying Kang

Publication date: 19 September 2007

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2006.12.027

zbMATH Keywords

algorithmblock graphclique-transversal setminus clique-transversal function

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (6)

Weighted maximum-clique transversal sets of graphs ⋮ Variations of maximum-clique transversal sets on graphs ⋮ Bounds on the clique-transversal number of regular graphs ⋮ Signed and minus clique-transversal functions on graphs ⋮ Signed clique-transversal functions in graphs ⋮ Dominating functions with integer values in graphs—a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum \(h\)-colourable subgraph problem in balanced graphs
• Clique-transversal sets of line graphs and complements of line graphs
• Covering all cliques of a graph
• Covering the cliques of a graph with vertices
• Lower bounds on the minus domination and \(k\)-subdomination numbers.
• On the clique-transversal number of chordal graphs
• An upper bound for the transversal numbers of 4-uniform hypergraphs
• On clique-transversals and clique-independent sets
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• The algorithmic complexity of minus domination in graphs
• Algorithmic aspects of clique-transversal and clique-independent sets
• Distance-hereditary graphs are clique-perfect

This page was built for publication: The algorithmic complexity of the minus clique-transversal problem