On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five

DOI10.1137/19M1249473zbMath1459.05234arXiv1903.04761OpenAlexW3038926908MaRDI QIDQ5854894

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

Publication date: 12 March 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

algorithmstable setindependent setholeperfect graphpotential maximal clique

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Perfect graphs (05C17)

Related Items (4)

Finding a shortest even hole in polynomial time ⋮ 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 ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs

Cites Work

• Unnamed Item
• The strong perfect graph theorem
• The ellipsoid method and its consequences in combinatorial optimization
• Listing all potential maximal cliques of a graph
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• Recognizing Berge graphs
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs
• Independent Set in P₅-Free Graphs in Polynomial Time

This page was built for publication: On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five