Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms

DOI10.1145/3379698zbMath1403.68337arXiv1705.01414OpenAlexW3033379983MaRDI QIDQ4608072

Roohani Sharma, Fahad Panolan, Daniel Lokshtanov, Saket Saurabh, Meirav Zehavi

Publication date: 15 March 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

parameterized algorithmsindependence covering familystable \(s\)-\(t\) separatorstable multicutstable OCT

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Randomized algorithms (68W20)

Related Items (5)

Parameterized complexity of conflict-free matchings and paths ⋮ Exploring the Kernelization Borders for Hitting Cycles ⋮ Unnamed Item ⋮ Conflict free version of covering problems on graphs: classical and parameterized ⋮ Parameterized complexity of conflict-free set cover

This page was built for publication: Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms