Stable sets of maximum weight in (P₇, banner)-free graphs

DOI10.1016/J.DISC.2007.03.044MaRDI QIDQ2463465zbMATH OpenOpenAlexFDO

Authors 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

(\(P_{7}\)banner)-free graphsmaximum weight stable set problempolynomial time algorithm

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(8)

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

This page was built for publication: Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs

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