New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths
DOI10.1134/S1990478918020023zbMATH Open1413.05273OpenAlexW2805481346MaRDI QIDQ4558286FDOQ4558286
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
Recommendations
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)
Cites Work
- Independent sets in extensions of 2\(K_{2}\)-free graphs
- Independent set in \(P_5\)-free graphs in polynomial time
- Some results on graphs without long induced paths
- Weighted independent sets in classes of \(P_6\)-free graphs
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- On the maximum independent set problem in subclasses of subcubic graphs
- Title not available (Why is that?)
- A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
- Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs
Cited In (5)
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)
