Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in H-Free Graphs

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

Title not available (Why is that?)
Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
Complement reducible graphs
Clique is hard to approximate within $n^{1-\epsilon}$
Title not available (Why is that?)
Approximation algorithms for NP-complete problems on planar graphs
Independent Set in P₅-Free Graphs in Polynomial Time
Title not available (Why is that?)
Some results on graphs without long induced paths
On maximal independent sets of vertices in claw-free graphs
The Rectilinear Steiner Tree Problem is $NP$-Complete
Title not available (Why is that?)
Stable sets in two subclasses of banner-free graphs
A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
A New Algorithm for the Maximum Weighted Stable Set Problem in Claw-Free Graphs
An $\mathcal{O}(m\log n)$ algorithm for the weighted stable set problem in claw-free graphs with $\alpha ({G}) \leq 3$
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
The three-in-a-tree problem
Title not available (Why is that?)
Stable sets of maximum weight in ($P_{7}$, banner)-free graphs
Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs
Title not available (Why is that?)
$H$-colouring $P_t$-free graphs in subexponential time
Subexponential-time algorithms for maximum independent set in $P_t$-free and broom-free graphs
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
A subexponential-time algorithm for the maximum independent set problem in $P_t$-free graphs
Finding large induced sparse subgraphs in c _>t -free graphs in quasipolynomial time
Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs
Title not available (Why is that?)

This page was built for publication: Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in $\boldsymbol{H}$-Free Graphs

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