Article ID Journal Published Year Pages File Type
426719 Information and Computation 2016 12 Pages PDF
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
, , ,