Weighted independent sets in classes of P₆-free graphs

DOI10.1016/J.DAM.2015.10.015MaRDI QIDQ298979zbMATH OpenOpenAlexFDO

Authors T. Karthick, Frédéric Maffray

Publication date 21 June 2016

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

Full work available at URL https://doi.org/10.1016/j.dam.2015.10.015

zbMATH Keywords

graph algorithmsmodular decompositionclaw-free graph\(P_6\)-free graphclique separatorweighted independent set

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Recommendations

• Weighted independent sets in a subclass of P₆-free graphs
• Independent Sets in Classes Related to Chair-Free Graphs
• Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
• Maximum weight independent sets in classes related to claw-free graphs
• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time

Cites work

• scientific article; zbMATH DE number 5761816 (Why is no real title available?)
• scientific article; zbMATH DE number 3908479 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 5279372 (Why is no real title available?)
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• A Linear Recognition Algorithm for Cographs
• A charming class of perfectly orderable graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Data Mining with optimized two-dimensional association rules
• Decomposition by clique separators
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Graph Classes: A Survey
• Independence and efficient domination on \(P_6\)-free graphs
• Independent sets of maximum weight in apple-free graphs
• Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
• Maximum weight independent sets in classes related to claw-free graphs
• Maximum weight independent sets in hole- and dart-free graphs
• Meyniel weakly triangulated graphs. I: Co-perfect orderability
• Modular decomposition and transitive orientation
• New applications of clique separator decomposition for the maximum weight stable set problem
• New graph classes of bounded clique-width
• On algorithms for (\(P_5\), gem)-free graphs
• On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• On diameters and radii of bridged graphs
• On maximal independent sets of vertices in claw-free graphs
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• Some results on graphs without long induced paths
• Stable sets in certain \(P_6\)-free graphs
• Stable sets in two subclasses of banner-free graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Vertex disjoint paths for dispatching in railways
• Weighted independent sets in a subclass of \(P_6\)-free graphs

Cited in

(18)

• 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
• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs
• Maximum weight independent sets in hole- and co-chair-free graphs
• Weighted independent sets in a subclass of \(P_6\)-free graphs
• Maximum weight independent sets in classes related to claw-free graphs
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• The exact weighted independent set problem in perfect graphs and related classes
• The maximum weight stable set problem in (\(P_6\), bull)-free graphs
• Independent Sets in Classes Related to Chair-Free Graphs
• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• Independence and efficient domination on \(P_6\)-free graphs
• New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths
• Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
• scientific article; zbMATH DE number 7742928 (Why is no real title available?)
• Independent sets in some classes of \(S_{i,j,k}\)-free graphs
• Vizing bound for the chromatic number on some graph classes
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs

This page was built for publication: Weighted independent sets in classes of \(P_6\)-free graphs

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