The algorithmic complexity of the minus clique-transversal problem

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

Research output: Journal article publicationJournal articleAcademic researchpeer-review

8 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 languageEnglish
Pages (from-to)1410-1418
Number of pages9
JournalApplied Mathematics and Computation
Volume189
Issue number2
DOIs
Publication statusPublished - 15 Jun 2007

Keywords

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

ASJC Scopus subject areas

  • Applied Mathematics
  • Computational Mathematics
  • Numerical Analysis

Cite this