The algorithmic complexity of the minus clique-transversal problem

Guangjun Xu; Erfang Shan; Liying Kang; Edwin Tai Chiu Cheng

doi:10.1016/j.amc.2006.12.027

The algorithmic complexity of the minus clique-transversal problem

Guangjun Xu, Erfang Shan, Liying Kang, Edwin Tai Chiu Cheng

Research output: Journal article publication › Journal article › Academic research › peer-review

10 Citations (Scopus)

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.

Original language	English
Pages (from-to)	1410-1418
Number of pages	9
Journal	Applied Mathematics and Computation
Volume	189
Issue number	2
DOIs	https://doi.org/10.1016/j.amc.2006.12.027
Publication status	Published - 15 Jun 2007

Keywords

Algorithm
Block graph
Clique-transversal set
Minus clique-transversal function

ASJC Scopus subject areas

Applied Mathematics
Computational Mathematics
Numerical Analysis

More information

10.1016/j.amc.2006.12.027

Cite this

@article{0428448299a04e0ab60f597f769120d3,

title = "The algorithmic complexity of the minus clique-transversal problem",

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

keywords = "Algorithm, Block graph, Clique-transversal set, Minus clique-transversal function",

author = "Guangjun Xu and Erfang Shan and Liying Kang and Cheng, {Edwin Tai Chiu}",

year = "2007",

month = jun,

day = "15",

doi = "10.1016/j.amc.2006.12.027",

language = "English",

volume = "189",

pages = "1410--1418",

journal = "Applied Mathematics and Computation",

issn = "0096-3003",

publisher = "Elsevier Inc.",

number = "2",

}

TY - JOUR

T1 - The algorithmic complexity of the minus clique-transversal problem

AU - Xu, Guangjun

AU - Shan, Erfang

AU - Kang, Liying

AU - Cheng, Edwin Tai Chiu

PY - 2007/6/15

Y1 - 2007/6/15

N2 - 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.

AB - 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.

KW - Algorithm

KW - Block graph

KW - Clique-transversal set

KW - Minus clique-transversal function

UR - http://www.scopus.com/inward/record.url?scp=34249106835&partnerID=8YFLogxK

U2 - 10.1016/j.amc.2006.12.027

DO - 10.1016/j.amc.2006.12.027

M3 - Journal article

SN - 0096-3003

VL - 189

SP - 1410

EP - 1418

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

IS - 2

ER -

The algorithmic complexity of the minus clique-transversal problem

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this