DC Field | Value | Language |
---|---|---|
dc.contributor.author | Oum, Sang-il | ko |
dc.contributor.author | Saether, Sigve Hortemo | ko |
dc.contributor.author | Vatshelle, Martin | ko |
dc.date.accessioned | 2014-09-01T07:15:06Z | - |
dc.date.available | 2014-09-01T07:15:06Z | - |
dc.date.created | 2014-06-23 | - |
dc.date.created | 2014-06-23 | - |
dc.date.issued | 2014-05 | - |
dc.identifier.citation | THEORETICAL COMPUTER SCIENCE, v.535, pp.16 - 24 | - |
dc.identifier.issn | 0304-3975 | - |
dc.identifier.uri | http://hdl.handle.net/10203/189192 | - |
dc.description.abstract | Many 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.language | English | - |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.subject | BRANCH-WIDTH | - |
dc.subject | DOMINATING SETS | - |
dc.subject | RANK-WIDTH | - |
dc.subject | GRAPHS | - |
dc.subject | DECOMPOSITION | - |
dc.subject | OBSTRUCTIONS | - |
dc.title | Faster algorithms for vertex partitioning problems parameterized by clique-width | - |
dc.type | Article | - |
dc.identifier.wosid | 000336354100002 | - |
dc.identifier.scopusid | 2-s2.0-84922314490 | - |
dc.type.rims | ART | - |
dc.citation.volume | 535 | - |
dc.citation.beginningpage | 16 | - |
dc.citation.endingpage | 24 | - |
dc.citation.publicationname | THEORETICAL COMPUTER SCIENCE | - |
dc.identifier.doi | 10.1016/j.tcs.2014.03.024 | - |
dc.embargo.liftdate | 9999-12-31 | - |
dc.embargo.terms | 9999-12-31 | - |
dc.contributor.localauthor | Oum, Sang-il | - |
dc.contributor.nonIdAuthor | Saether, Sigve Hortemo | - |
dc.contributor.nonIdAuthor | Vatshelle, Martin | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Clique-width | - |
dc.subject.keywordAuthor | Parameterized complexity | - |
dc.subject.keywordAuthor | Dynamic programming | - |
dc.subject.keywordAuthor | Generalized domination | - |
dc.subject.keywordAuthor | Rank-width | - |
dc.subject.keywordPlus | BRANCH-WIDTH | - |
dc.subject.keywordPlus | DOMINATING SETS | - |
dc.subject.keywordPlus | RANK-WIDTH | - |
dc.subject.keywordPlus | GRAPHS | - |
dc.subject.keywordPlus | DECOMPOSITION | - |
dc.subject.keywordPlus | OBSTRUCTIONS | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.