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

DOI10.1016/j.ic.2015.11.002zbMath1336.68119arXiv1304.5870OpenAlexW1812795470WikidataQ60488380 ScholiaQ60488380MaRDI QIDQ259037

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

Publication date: 10 March 2016

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.5870

zbMATH Keywords

directed graphsparameterized complexityanchored \(k\)-core

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Directed graphs (digraphs), tournaments (05C20)

Related Items

A parameterized complexity view on collapsing \(k\)-cores ⋮ Building large \(k\)-cores from sparse graphs ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Parameterized graph separation problems
• Computing small partial coverings
• Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
• Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs
• Preventing Unraveling in Social Networks: The Anchored k-Core Problem
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• The Complexity of Multiterminal Cuts
• Color-coding
• Communication and Coordination in Social Networks
• Parameterized Algorithms
• Depth-First Search and Linear Graph Algorithms

This page was built for publication: Parameterized complexity of the anchored \(k\)-core problem for directed graphs