New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths

DOI10.1134/S1990478918020023zbMath1413.05273OpenAlexW2805481346MaRDI QIDQ4558286

S. V. Sorochan, Vladimir 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 setpathsupergraphpolynomial timeforbidden subgraph

Mathematics Subject Classification ID

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

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Weighted independent sets in classes of \(P_6\)-free graphs
• Some results on graphs without long induced paths
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• On the maximum independent set problem in subclasses of subcubic graphs
• A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
• 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
• Independent Set in P₅-Free Graphs in Polynomial Time

This page was built for publication: New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths