Covering Small Independent Sets and Separators with Applications to Parameterized Algorithms

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

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

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 algorithms; independence covering family; stable \(s\)-\(t\) separator; stable multicut; stable OCT

Mathematics Subject Classification ID

68W40: Analysis of algorithms

68W05: Nonnumerical algorithms

68R10: Graph theory (including graph drawing) in computer science

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

68W20: Randomized algorithms