Weighted independent sets in classes of \(P_6\)-free graphs

DOI10.1016/J.DAM.2015.10.015zbMath1339.05170OpenAlexW2190717998MaRDI QIDQ298979

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

claw-free graphgraph algorithmsmodular decomposition\(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)

Related Items (8)

Vizing bound for the chromatic number on some graph classes ⋮ The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs ⋮ New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs ⋮ Unnamed Item ⋮ Independent Sets in Classes Related to Chair-Free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximum weight independent sets in classes related to claw-free graphs
• On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Meyniel weakly triangulated graphs. I: Co-perfect orderability
• Maximum weight independent sets in hole- and dart-free graphs
• New graph classes of bounded clique-width
• On algorithms for (\(P_5\), gem)-free graphs
• New applications of clique separator decomposition for the maximum weight stable set problem
• Weighted independent sets in a subclass of \(P_6\)-free graphs
• Some results on graphs without long induced paths
• Decomposition by clique separators
• On diameters and radii of bridged graphs
• On maximal independent sets of vertices in claw-free graphs
• The ellipsoid method and its consequences in combinatorial optimization
• A charming class of perfectly orderable graphs
• Modular decomposition and transitive orientation
• Stable sets in certain \(P_6\)-free graphs
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• Stable sets in two subclasses of banner-free graphs
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• Vertex Disjoint Paths for Dispatching in Railways.
• Data Mining with optimized two-dimensional association rules
• A Linear Recognition Algorithm for Cographs
• Graph Classes: A Survey
• Independence and Efficient Domination on P₆-free Graphs
• Independent Sets of Maximum Weight in Apple-Free Graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

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