Stable sets in certain P₆-free graphs
From MaRDI portal
Publication:1304476
DOI10.1016/S0166-218X(99)00046-3zbMATH Open0929.05076MaRDI QIDQ1304476FDOQ1304476
Authors: Raffaele Mosca 
Publication date: 11 January 2000
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Recommendations
- Maximum independent sets in subclasses of \(P_{5}\)-free graphs
- On maximum independent sets in \(P_{5}\)-free graphs
- Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
- Some results on stable sets for \(k\)-colorable \(P_{6}\)-free graphs and generalizations
- Independent set in \(P_5\)-free graphs in polynomial time
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
- 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
- On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
- Stability number of bull- and chair-free graphs
- The complexity of comparability graph recognition and coloring
- Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free 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
- Paw-free graphs
- A characterization of graphs without long induced paths
Cited In (26)
- On independent vertex sets in subclasses of apple-free graphs
- Stable sets for (P_{6}, K_{2,3})-free graphs
- The maximum weight stable set problem in (\(P_6\), bull)-free graphs
- On maximum independent sets in \(P_{5}\)-free graphs
- Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs
- Weighted independent sets in classes of \(P_6\)-free graphs
- On finding augmenting graphs
- From matchings to independent sets
- Combinatorics and algorithms for augmenting graphs
- New applications of clique separator decomposition for the maximum weight stable set problem
- Partitioning graphs into connected parts
- Partitioning Graphs into Connected Parts
- Stable sets in two subclasses of banner-free graphs
- Finding augmenting chains in extensions of claw-free graphs
- Maximum independent sets in subclasses of \(P_{5}\)-free graphs
- Parameterized algorithms for the independent set problem in some hereditary graph classes
- Some new hereditary classes where graph coloring remains NP-hard
- \(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
- Square-Free Graphs with No Six-Vertex Induced Path
- Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Augmenting graphs for independent sets
- Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
- Independent Sets in Classes Related to Chair-Free Graphs
- A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
This page was built for publication: Stable sets in certain \(P_6\)-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1304476)
