Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs

DOI10.1137/1.9781611975994.139OpenAlexW4239839953MaRDI QIDQ5146928

Maria Chudnovsky, Michał Pilipczuk, Marcin Pilipczuk, Steéphan Thomassé

Publication date: 2 February 2021

Published in: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (9)

Degeneracy of \(P_t\)-free and \(C_{\geq t}\)-free graphs with no large complete bipartite subgraphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs ⋮ Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ Parameterized inapproximability of independent set in \(H\)-free graphs ⋮ On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five

This page was built for publication: Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs