A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
From MaRDI portal
Publication:2403797
DOI10.1016/j.dam.2016.06.016zbMath1369.05159OpenAlexW2484570912MaRDI QIDQ2403797
Publication date: 12 September 2017
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2016.06.016
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (11)
New results on independent sets in extensions of \(2K_2\)-free graphs ⋮ Combining decomposition approaches for the maximum weight stable set problem ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Unnamed Item ⋮ Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs ⋮ Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs ⋮ Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ A note on the fine-grained complexity of MIS on regular graphs ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ \(H\)-colouring \(P_t\)-free graphs in subexponential time
Cites Work
- On maximum independent sets in \(P_{5}\)-free graphs
- A new characterization of \(P_{6}\)-free graphs
- Some results on graphs without long induced paths
- Stable sets in certain \(P_6\)-free graphs
- Which problems have strongly exponential complexity?
- Independence and Efficient Domination on P6-free Graphs
- Polynomial algorithm for finding the largest independent sets in graphs without forks
- On the complexity of \(k\)-SAT
- Unnamed Item
- Unnamed Item
This page was built for publication: A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
