Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/33140
Title: The algorithmic complexity of the minus clique-transversal problem
Authors: Xu, G
Shan, E
Kang, L
Cheng, TCE 
Keywords: Algorithm
Block graph
Clique-transversal set
Minus clique-transversal function
Issue Date: 2007
Publisher: Elsevier
Source: Applied mathematics and computation, 2007, v. 189, no. 2, p. 1410-1418 How to cite?
Journal: Applied mathematics and computation 
Abstract: A minus clique-transversal function of a graph G = (V, E) is a function f : V → {- 1, 0, 1} such that ∑u ∈ V (C) f (u) ≥ 1 for every clique C of G. The weight of a minus clique-transversal function is f (V) = ∑ f (v), over all vertices v ∈ V. The minus clique-transversal number of a graph G, denoted τc - (G), equals the minimum weight of a minus clique-transversal function of G. The upper minus clique-transversal number of a graph G, denoted Tc - (G), equals the maximum weight of a minimal minus clique-transversal function of G. In this paper, we show that the minus clique-transversal problem (respectively, upper minus clique-transversal problem) is NP-complete even when restricted to chordal graphs. On the other hand, we give a linear algorithm to solve the minus clique-transversal problem for block graphs.
URI: http://hdl.handle.net/10397/33140
ISSN: 0096-3003
EISSN: 1873-5649
DOI: 10.1016/j.amc.2006.12.027
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

7
Last Week
0
Last month
0
Citations as of Aug 11, 2017

WEB OF SCIENCETM
Citations

6
Last Week
0
Last month
0
Citations as of Aug 13, 2017

Page view(s)

68
Last Week
1
Last month
Checked on Aug 13, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.