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

4 Citations (Scopus)

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

@article{3ab3124be63445889292c2e6491a07e7,
title = "Tight complexity bounds for FPT subgraph problems parameterized by the clique-width",
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.",
keywords = "MSC-05C, Parameterized complexity, Subgraph problems, IR-86132, Clique-width, Exponential time hypothesis, METIS-297655, EWI-23371",
author = "Broersma, {Haitze J.} and Golovach, {Petr A.} and Viresh Patel",
note = "eemcs-eprint-23371",
year = "2013",
doi = "10.1016/j.tcs.2013.03.008",
language = "Undefined",
volume = "485",
pages = "69--84",
journal = "Theoretical computer science",
issn = "0304-3975",
publisher = "Elsevier",

}

Tight complexity bounds for FPT subgraph problems parameterized by the clique-width. / Broersma, Haitze J.; Golovach, Petr A.; Patel, Viresh.

In: Theoretical computer science, Vol. 485, 2013, p. 69-84.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

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

AU - Broersma, Haitze J.

AU - Golovach, Petr A.

AU - Patel, Viresh

N1 - eemcs-eprint-23371

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - MSC-05C

KW - Parameterized complexity

KW - Subgraph problems

KW - IR-86132

KW - Clique-width

KW - Exponential time hypothesis

KW - METIS-297655

KW - EWI-23371

U2 - 10.1016/j.tcs.2013.03.008

DO - 10.1016/j.tcs.2013.03.008

M3 - Article

VL - 485

SP - 69

EP - 84

JO - Theoretical computer science

JF - Theoretical computer science

SN - 0304-3975

ER -