The algorithmic complexity of the minus clique-transversal problem

DOI10.1016/J.AMC.2006.12.027MaRDI QIDQ2383654zbMATH OpenOpenAlexFDO

Authors Guangjun Xu, Erfang Shan, Liying Kang, T. C. Edwin Cheng

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

Recommendations

• The algorithmic complexity of minus domination in graphs
• Approximation algorithms for clique transversals on some graph classes
• Algorithms for finding clique-transversals of graphs
• The complexity of the vertex-minor problem
• Algorithmic aspects of clique-transversal and clique-independent sets
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• Algorithmic lower bounds for problems parameterized by clique-width
• Approximability of clique transversal in perfect graphs
• Algorithmic aspects of minus total \(k\)-subdomination in graphs
• Approximation algorithms on \(k\)-cycle transversal and \(k\)-clique transversal

Cites work

• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• scientific article; zbMATH DE number 861332 (Why is no real title available?)
• Algorithmic aspects of clique-transversal and clique-independent sets
• Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
• An upper bound for the transversal numbers of 4-uniform hypergraphs
• Clique domination in 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
• Distance-hereditary graphs are clique-perfect
• Graph theory
• Lower bounds on the minus domination and \(k\)-subdomination numbers.
• Maximum \(h\)-colourable subgraph problem in balanced graphs
• On clique-transversals and clique-independent sets
• On the clique-transversal number of chordal graphs
• The algorithmic complexity of minus domination in graphs

Cited in

(8)

• Weighted maximum-clique transversal sets of graphs
• Signed and minus clique-transversal functions on graphs
• Bounds on the clique-transversal number of regular graphs
• Dominating functions with integer values in graphs—a survey
• Variations of maximum-clique transversal sets on graphs
• Signed clique-transversal functions in graphs
• The complexity of the vertex-minor problem
• Subtraction-free complexity, cluster transformations, and spanning trees

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2383654)