Polynomial-time Algorithm for Maximum Weight Independent Set on P 6 -free Graphs

DOI10.1145/3414473MaRDI QIDQ6058231

Marcin Pilipczuk, Andrzej Grzesik, Michał Pilipczuk, Tereza Klimošová

Publication date: 31 October 2023

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

zbMATH Keywords

maximum independent set\(P_6\)-free graphspotential maximal clique

Mathematics Subject Classification ID

Computer science (68-XX)

Related Items (5)

Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs ⋮ Few induced disjoint paths for \(H\)-free graphs

This page was built for publication: Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs