Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs
From MaRDI portal
Publication:6203477
DOI10.1137/20m1333778OpenAlexW4391998821MaRDI QIDQ6203477
Maria Chudnovsky, Steéphan Thomassé, Michał Pilipczuk, Marcin Pilipczuk
Publication date: 28 February 2024
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/20m1333778
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The three-in-a-tree problem
- Some results on graphs without long induced paths
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- Complement reducible graphs
- Stable sets in two subclasses of banner-free graphs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time
- Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
- Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- An \(\mathcal{O}(m\log n)\) algorithm for the weighted stable set problem in claw-free graphs with \(\alpha ({G}) \leq 3\)
- A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
- Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs
- A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- Approximation algorithms for NP-complete problems on planar graphs
- Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
- Independent Set in P5-Free Graphs in Polynomial Time
- Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition
- On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five
- A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
- Polynomial-time Algorithm for Maximum Weight Independent Set on P 6 -free Graphs
- Finding large induced sparse subgraphs in c >t -free graphs in quasipolynomial time
This page was built for publication: Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs