Faster algorithms for vertex partitioning problems parameterized by clique-width

Cited 14 time in webofscience Cited 16 time in scopus
  • Hit : 513
  • Download : 159
DC FieldValueLanguage
dc.contributor.authorOum, Sang-ilko
dc.contributor.authorSaether, Sigve Hortemoko
dc.contributor.authorVatshelle, Martinko
dc.date.accessioned2014-09-01T07:15:06Z-
dc.date.available2014-09-01T07:15:06Z-
dc.date.created2014-06-23-
dc.date.created2014-06-23-
dc.date.issued2014-05-
dc.identifier.citationTHEORETICAL COMPUTER SCIENCE, v.535, pp.16 - 24-
dc.identifier.issn0304-3975-
dc.identifier.urihttp://hdl.handle.net/10203/189192-
dc.description.abstractMany NP-hard problems, such as DOMINATING SET, are FPT parameterized by clique-width. For graphs of clique-width k given with a k-expression, DOMINATING SET can be solved in 4(k)n(O(1)) time. However, no FPT algorithm is known for computing an optimal k-expression. For a graph of clique-width k, if we rely on known algorithms to compute a (2(3k)-1)-expression via rank-width and then solving DOMINATING SET using the (2(3k)-1)-expression, the above algorithm will only give a runtime of 4(23k)n(O(1)). There have been results which overcome this exponential jump; the best known algorithm can solve DOMINATING SET in time 2(O(k2))n(O(1)) by avoiding constructing a k-expression Bui-Xuan et al. (2013) [7]. We improve this to 2O((k logk))n(O(1)). Indeed, we show that for a graph of clique-width k, a large class of domination and partitioning problems (LC-VSP), including DOMINATING SET, can be solved in 2(O(k log k))n(O(1)). Our main tool is a variant of rank-width using the rank of a 0-1 matrix over the rational field instead of the binary field.-
dc.languageEnglish-
dc.publisherELSEVIER SCIENCE BV-
dc.subjectBRANCH-WIDTH-
dc.subjectDOMINATING SETS-
dc.subjectRANK-WIDTH-
dc.subjectGRAPHS-
dc.subjectDECOMPOSITION-
dc.subjectOBSTRUCTIONS-
dc.titleFaster algorithms for vertex partitioning problems parameterized by clique-width-
dc.typeArticle-
dc.identifier.wosid000336354100002-
dc.identifier.scopusid2-s2.0-84922314490-
dc.type.rimsART-
dc.citation.volume535-
dc.citation.beginningpage16-
dc.citation.endingpage24-
dc.citation.publicationnameTHEORETICAL COMPUTER SCIENCE-
dc.identifier.doi10.1016/j.tcs.2014.03.024-
dc.embargo.liftdate9999-12-31-
dc.embargo.terms9999-12-31-
dc.contributor.localauthorOum, Sang-il-
dc.contributor.nonIdAuthorSaether, Sigve Hortemo-
dc.contributor.nonIdAuthorVatshelle, Martin-
dc.type.journalArticleArticle-
dc.subject.keywordAuthorClique-width-
dc.subject.keywordAuthorParameterized complexity-
dc.subject.keywordAuthorDynamic programming-
dc.subject.keywordAuthorGeneralized domination-
dc.subject.keywordAuthorRank-width-
dc.subject.keywordPlusBRANCH-WIDTH-
dc.subject.keywordPlusDOMINATING SETS-
dc.subject.keywordPlusRANK-WIDTH-
dc.subject.keywordPlusGRAPHS-
dc.subject.keywordPlusDECOMPOSITION-
dc.subject.keywordPlusOBSTRUCTIONS-
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 14 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0