Parameterized complexity of the anchored k-core problem for directed graphs
Research output: Contribution to journal › Article › peer-review
Colleges, School and Institutes
- University of Bergen
- Weizmann Institute of Science, Rehovot, Israel.
- Russian Academy of Sciences, St. Pertersburg, Russia
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.
|Journal||Information and Computation|
|Early online date||1 Dec 2015|
|Publication status||Published - 1 Apr 2016|