Finding minimum clique capacity

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 340
  • Download : 0
DC FieldValueLanguage
dc.contributor.authorChudnovsky, Mariako
dc.contributor.authorOum, Sang-ilko
dc.contributor.authorSeymour, Paulko
dc.date.accessioned2013-03-12T21:39:14Z-
dc.date.available2013-03-12T21:39:14Z-
dc.date.created2012-10-09-
dc.date.created2012-10-09-
dc.date.created2012-10-09-
dc.date.issued2012-04-
dc.identifier.citationCOMBINATORICA, v.32, no.3, pp.283 - 287-
dc.identifier.issn0209-9683-
dc.identifier.urihttp://hdl.handle.net/10203/103598-
dc.description.abstractLet 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.-
dc.languageEnglish-
dc.publisherSPRINGER-
dc.titleFinding minimum clique capacity-
dc.typeArticle-
dc.identifier.wosid000308285700002-
dc.identifier.scopusid2-s2.0-84865810649-
dc.type.rimsART-
dc.citation.volume32-
dc.citation.issue3-
dc.citation.beginningpage283-
dc.citation.endingpage287-
dc.citation.publicationnameCOMBINATORICA-
dc.identifier.doi10.1007/s00493-012-2891-9-
dc.contributor.localauthorOum, Sang-il-
dc.contributor.nonIdAuthorChudnovsky, Maria-
dc.contributor.nonIdAuthorSeymour, Paul-
dc.description.isOpenAccessN-
dc.type.journalArticleArticle-
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