On maximum independent sets in P₅-free graphs

DOI10.1016/J.DAM.2010.01.007zbMATH Open1210.05164OpenAlexW2048280336MaRDI QIDQ708334FDOQ708334

Authors Bert Randerath, Ingo Schiermeyer

Publication date 11 October 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.01.007

zbMATH Keywords

independent setindependence numbersubexponential algorithms

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• Independent set in \(P_5\)-free graphs in polynomial time
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• Stable sets in certain \(P_6\)-free graphs
• On the stable set problem in special \(P_{5}\)-free graphs

Cites work

• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• A New Characterization of P 6-Free Graphs
• Complete description of forbidden subgraphs in the structural domination problem
• Dominating cliques in \(P_ 5\)-free graphs
• Hereditary Domination in Graphs: Characterization with Forbidden Induced Subgraphs
• Measure and conquer

Cited in

(16)

• On mirror nodes in graphs without long induced paths
• Independent set in \(P_5\)-free graphs in polynomial time
• Spectral properties of cographs and \(P_5\)-free graphs
• scientific article; zbMATH DE number 3941587 (Why is no real title available?)
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
• A note on the fine-grained complexity of MIS on regular graphs
• Maximum independent sets in subclasses of \(P_{5}\)-free graphs
• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• An exact algorithm for maximum independent set in degree-5 graphs
• Maximizing five-cycles in \(K_r\)-free graphs
• H-free graphs, independent sets, and subexponential-time algorithms
• Independent Feedback Vertex Set for P_5-free Graphs
• Independent domination in finitely defined classes of graphs: polynomial algorithms
• Tent and a subclass of \(P_{5}\)-free graphs
• An Exact Algorithm for Maximum Independent Set in Degree-5 Graphs
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs

This page was built for publication: On maximum independent sets in \(P_{5}\)-free graphs

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