New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths

DOI10.1134/S1990478918020023MaRDI QIDQ4558286zbMATH OpenOpenAlexFDO

Authors S. V. Sorochan, V. E. Alekseev

Publication date 21 November 2018

Published in Journal of Applied and Industrial Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s1990478918020023

zbMATH Keywords

independent setpolynomial timepathforbidden subgraphsupergraph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
• scientific article; zbMATH DE number 7742928
• Some results on graphs without long induced paths
• scientific article; zbMATH DE number 6460018
• scientific article; zbMATH DE number 468640

Cites work

• scientific article; zbMATH DE number 468640 (Why is no real title available?)
• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• Independent set in \(P_5\)-free graphs in polynomial time
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• On the maximum independent set problem in subclasses of subcubic graphs
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
• Some results on graphs without long induced paths
• Weighted independent sets in classes of \(P_6\)-free graphs

Cited in

(5)

• scientific article; zbMATH DE number 6460018 (Why is no real title available?)
• Some results on graphs without long induced paths
• Independent sets in the graphs with bounded minors of the extended incidence matrix
• scientific article; zbMATH DE number 468640 (Why is no real title available?)
• scientific article; zbMATH DE number 7742928 (Why is no real title available?)

This page was built for publication: New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths

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