Tight complexity bounds for FPT subgraph problems parameterized by the clique-width

Haitze J. Broersma, Petr A. Golovach, Viresh Patel

Research output: Contribution to journalArticleAcademicpeer-review

18 Citations (Scopus)
12 Downloads (Pure)

Abstract

We give tight algorithmic lower and upper bounds for some double-parameterized subgraph problems when the clique-width of the input graph is one of the parameters.
Original languageUndefined
Pages (from-to)69-84
Number of pages16
JournalTheoretical computer science
Volume485
DOIs
Publication statusPublished - 2013

Keywords

  • MSC-05C
  • Parameterized complexity
  • Subgraph problems
  • IR-86132
  • Clique-width
  • Exponential time hypothesis
  • METIS-297655
  • EWI-23371

Cite this