Max weight independent set in graphs with no long claws: an analog of the Gyárfás' path argument

DOI10.4230/LIPICS.ICALP.2022.93MaRDI QIDQ6560891FDOQ6560891

Authors: Konrad Majewski, Tomáš Masařík, Jana Novotná, Karolina Okrasa, Marcin Pilipczuk, Paweł Rzążewski, Marek Sokołowski 

Publication date: 24 June 2024

Recommendations

• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• Independent Sets of Maximum Weight in Apple-Free Graphs
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs

zbMATH Keywords

subdivided clawsubexponential-time algorithmmax independent setQPTAS

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

This page was built for publication: Max weight independent set in graphs with no long claws: an analog of the Gyárfás' path argument

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6560891)