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

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

Review text

A minus clique-transversal function, MCTF for short, of a graph \(G=(V,E)\) is a function \(f:V\rightarrow \{-1,0,1\}\) such that \(\sum_{u\in V(C)}f(u)\geq 1\) for every clique \(C\) in \(G\). The weight of an MCTF \(f\) is \(\sum_{v\in V}f(v)\). The minus clique-transversal number of a graph \(G\) equals the minimum weight of an MCTF of \(G\). The upper minus clique-transversal number of a graph \(G\) equals to the maximum weight of a minimal MCTF of \(G\).

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

• 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
• 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?)
• 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)

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

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)