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

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

doi:10.1016/j.ic.2015.11.002

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

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

^*Corresponding author for this work

Computer Science

Research output: Contribution to journal › Article › peer-review

11 Citations (Scopus)

125 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 language	English
Pages (from-to)	11-22
Journal	Information and Computation
Volume	247
Early online date	1 Dec 2015
DOIs	https://doi.org/10.1016/j.ic.2015.11.002
Publication status	Published - 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

Access to Document

10.1016/j.ic.2015.11.002Licence: None: All rights reserved

Chitnis_parameterized_complexity_information_and_computation_2016Accepted author manuscript, 400 KBLicence: Other (please provide link to licence statement

Cite this

@article{016f3f548a9449c89fcbb9b2d50ae642,

title = "Parameterized complexity of the anchored k-core problem for directed graphs",

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.",

keywords = "Anchored k-core, Directed graphs, Parameterized complexity",

author = "Rajesh Chitnis and Fomin, {Fedor V.} and Golovach, {Petr A.}",

year = "2016",

month = apr,

day = "1",

doi = "10.1016/j.ic.2015.11.002",

language = "English",

volume = "247",

pages = "11--22",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier",

}

TY - JOUR

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

AU - Chitnis, Rajesh

AU - Fomin, Fedor V.

AU - Golovach, Petr A.

PY - 2016/4/1

Y1 - 2016/4/1

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

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

KW - Anchored k-core

KW - Directed graphs

KW - Parameterized complexity

UR - http://www.scopus.com/inward/record.url?scp=84959514696&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2015.11.002

DO - 10.1016/j.ic.2015.11.002

M3 - Article

AN - SCOPUS:84959514696

SN - 0890-5401

VL - 247

SP - 11

EP - 22

JO - Information and Computation

JF - Information and Computation

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this