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)

Recommendations

On the stable set problem in special $P_{5}$-free graphs
Some observations on maximum weight stable sets in certain $P_{5}$-free graphs
scientific article; zbMATH DE number 1839471
Some results on maximum stable sets in certain $P_{5}$-free graphs
$P_{5}$-free augmenting graphs and the maximum stable set problem

Cites work

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

Cited in

(28)

Maximum weight independent sets in hole- and co-chair-free graphs
scientific article; zbMATH DE number 2190095 (Why is no real title available?)
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
Some results on graphs without long induced paths
Stability in $P_5$- and banner-free graphs
Augmenting chains in graphs without a skew star.
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)