Polynomial algorithms for the maximum stable set problem on particular classes of P₅-free graphs

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Structural characterization of families of graphs (05C75)

Cites Work

Title not available (Why is that?)
Geometric algorithms and combinatorial optimization
Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
Some simplified NP-complete graph problems
On maximal independent sets of vertices in claw-free graphs
Dominating cliques in $P_ 5$-free graphs
The complexity of generalized clique packing
Stability number of bull- and chair-free graphs
The complexity of comparability graph recognition and coloring
New classes of Berge perfect graphs
Title not available (Why is that?)
The Rectilinear Steiner Tree Problem is $NP$-Complete
Title not available (Why is that?)
A Graph-Theoretic Approach to a Class of Integer-Programming Problems

Cited In (28)

Maximum weight independent sets in hole- and co-chair-free graphs
Title not available (Why is that?)
Struction revisited
On the stable set problem in special $P_{5}$-free graphs
Stability number in subclasses of $P_5$-free graphs
Robust algorithms for the stable set problem
On easy and hard hereditary classes of graphs with respect to the independent set problem
On atomic structure of $P_5$-free subclasses and maximum weight independent set problem
Augmenting chains in graphs without a skew star.
Stability in $P_5$- and banner-free graphs
Some results on graphs without long induced paths
Independent sets in extensions of 2$K_{2}$-free graphs
New applications of clique separator decomposition for the maximum weight stable set problem
Some observations on maximum weight stable sets in certain $P_{5}$-free graphs
Stable sets in certain $P_6$-free graphs
On the structure and stability number of $P_{5}$- and co-chair-free graphs
Stable sets in two subclasses of banner-free graphs
A note on $\alpha$-redundant vertices in graphs
Finding augmenting chains in extensions of claw-free graphs
Maximum independent sets in subclasses of $P_{5}$-free graphs
$P_{5}$-free augmenting graphs and the maximum stable set problem
An augmenting graph approach to the stable set problem in $P_{5}$-free graphs
A note on the computational complexity of graph vertex partition
On $\alpha$-redundant vertices in $P_{5}$-free graphs
Augmenting graphs for independent sets
Some results on maximum stable sets in certain $P_{5}$-free graphs
Fundamentals of Computation Theory
New sufficient conditions for $\alpha$-redundant vertices

This page was built for publication: Polynomial algorithms for the maximum stable set problem on particular classes of $P_{5}$-free graphs

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