Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426719 | Information and Computation | 2016 | 12 Pages |
Abstract
We consider the Directed Anchoredk-Core problem, where the task is for a given directed graph G and integers b,kb,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 Anchoredk-Core problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Rajesh Chitnis, Fedor V. Fomin, Petr A. Golovach,