Parameterized complexity of the anchored k-core problem for directed graphs

Rajesh Chitnis, Fedor V. Fomin, Petr A. Golovach

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)
69 Downloads (Pure)

Abstract

We consider the Directed Anchored k-Core problem, where the task is for a given directed graph G and integers b,k and p, to find an induced subgraph H with at least p vertices (the core) such that all but at most b vertices (the anchors) of H have in-degree at least k. We undertake a systematic analysis of the computational complexity of the Directed Anchored k-Core problem.

Original languageEnglish
Pages (from-to)11-22
JournalInformation and Computation
Volume247
Early online date1 Dec 2015
DOIs
Publication statusPublished - 1 Apr 2016

Keywords

  • Anchored k-core
  • Directed graphs
  • Parameterized complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Parameterized complexity of the anchored k-core problem for directed graphs'. Together they form a unique fingerprint.

Cite this