Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs

DOI10.1016/j.disc.2007.03.044zbMath1127.05098OpenAlexW2015311674MaRDI QIDQ2463465

Raffaele Mosca

Publication date: 12 December 2007

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2007.03.044

zbMATH Keywords

polynomial time algorithmmaximum weight stable set problem(\(P_{7}\)banner)-free graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

On independent vertex sets in subclasses of apple-free graphs, Combining decomposition approaches for the maximum weight stable set problem, Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time, Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs, Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs, Complexity results for equistable graphs and related classes, Improved complexity results on \(k\)-coloring \(P_t\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Augmenting graphs for independent sets
• Finding augmenting chains in extensions of claw-free graphs
• Some results on graphs without long induced paths
• Decomposition by clique separators
• Polytope des independants d'un graphe série-parallèle
• An algorithm for finding clique cut-sets
• Dominating cliques in \(P_ 5\)-free graphs
• Some simplified NP-complete graph problems
• Modular decomposition and transitive orientation
• Stable sets in certain \(P_6\)-free graphs
• On easy and hard hereditary classes of graphs with respect to the independent set problem
• Stable sets in two subclasses of banner-free graphs
• Stability in \(P_5\)- and banner-free graphs
• A characterization of graphs without long induced paths
• On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• On the diameter ofi-center in a graph without long induced paths
• Graph Classes: A Survey
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• A note on \(\alpha\)-redundant vertices in graphs