Independence and Efficient Domination on P 6 -free Graphs

DOI10.1145/3147214zbMath1431.68049arXiv1507.02163OpenAlexW2773660891MaRDI QIDQ4554948

Marcin Pilipczuk, Daniel Lokshtanov, Erik Jan van Leeuwen

Publication date: 12 November 2018

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

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

zbMATH Keywords

independenceefficient domination\(P_6\)-free graphs(quasi)polynomial-time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ Excluding hooks and their complements ⋮ Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs ⋮ Maximum weight independent sets for (\(S_{1,2,4}\),triangle)-free graphs in polynomial time

This page was built for publication: Independence and Efficient Domination on P ₆ -free Graphs