Finding minimum clique capacity

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 326
  • Download : 0
Let C be a clique of a graph G. The capacity of C is defined to be (|V (G)\C|+|D|)/2, where D is the set of vertices in V (G)\C that have both a neighbour and a non-neighbour in C. We give a polynomial-time algorithm to find the minimum clique capacity in a graph G. This problem arose in the study [1] of packing vertex-disjoint induced three-vertex paths in a graph with no stable set of size three, which in turn was motivated by Hadwiger's conjecture.
Publisher
SPRINGER
Issue Date
2012-04
Language
English
Article Type
Article
Citation

COMBINATORICA, v.32, no.3, pp.283 - 287

ISSN
0209-9683
DOI
10.1007/s00493-012-2891-9
URI
http://hdl.handle.net/10203/103598
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0