Some observations on maximum weight stable sets in certain $P_{5}$-free graphs

DOI10.1016/j.ejor.2006.12.011zbMath1141.05068OpenAlexW2077506848MaRDI QIDQ2384837

Publication date: 10 October 2007

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2006.12.011

zbMATH Keywords

polynomial time algorithm $P_{5}$-free graphs Maximum weight stable set problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Boundary graph classes for some maximum induced subgraph problems ⋮ Independent domination in finitely defined classes of graphs: polynomial algorithms ⋮ Maximum independent sets in subclasses of $P_{5}$-free graphs

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Polynomial algorithms for the maximum stable set problem on particular classes of $P_{5}$-free graphs
On algorithms for ($P_5$, gem)-free graphs
On diameters and radii of bridged graphs
On maximal independent sets of vertices in claw-free graphs
Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
Dominating cliques in $P_ 5$-free graphs
Some simplified NP-complete graph problems
Modular decomposition and transitive orientation
On the stability number of claw-free $P_5$-free and more general graphs
Parallel concepts in graph theory
Weighted parameters in $(P_5,\overline {P_5})$-free graphs
On easy and hard hereditary classes of graphs with respect to the independent set problem
On the structure and stability number of $P_{5}$- and co-chair-free graphs
Some results on maximum stable sets in certain $P_{5}$-free graphs
Stability in $P_5$- and banner-free graphs
Independent sets in extensions of 2$K_{2}$-free graphs
On the stable set problem in special $P_{5}$-free graphs
On graphs without $P_ 5$ and $\overline {P}_ 5$
On the vertex packing problem
A characterization of graphs without long induced paths
On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem
A Linear Recognition Algorithm for Cographs
The Rectilinear Steiner Tree Problem is $NP$-Complete
On the diameter ofi-center in a graph without long induced paths
Graph Classes: A Survey
A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
Polynomial algorithm for finding the largest independent sets in graphs without forks
Fundamentals of Computation Theory
A note on $\alpha$-redundant vertices in graphs

This page was built for publication: Some observations on maximum weight stable sets in certain $P_{5}$-free graphs

Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs