Weighted independent sets in a subclass of P₆-free graphs

DOI10.1016/J.DISC.2015.12.008MaRDI QIDQ906493zbMATH OpenOpenAlexFDO

Authors T. Karthick

Publication date 21 January 2016

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.05401

zbMATH Keywords

graph algorithmsindependent sets\(P_6\)-free graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Abstract: The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for $P_6$-free graphs is unknown. In this note, we show that the MWIS problem can be solved in time $O(n^{3}m)$ for ($P_6$, banner)-free graphs by analyzing the structure of subclasses of these class of graphs. This extends the existing results for ($P_5$, banner)-free graphs, and ($P_6$, $C_4$)-free graphs. Here, $P_t$ denotes the chordless path on $t$ vertices, and a banner is the graph obtained from a chordless cycle on four vertices by adding a vertex that has exactly one neighbor on the cycle.

Recommendations

• Maximum weight independent sets in (P₆, co-banner)-free graphs
• Weighted independent sets in classes of \(P_6\)-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
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• A Linear Recognition Algorithm for Cographs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Computing independent sets in graphs with large girth
• Data Mining with optimized two-dimensional association rules
• Decomposition by clique separators
• Graph Classes: A Survey
• Graphs without large apples and the maximum weight independent set problem
• Independence and efficient domination on \(P_6\)-free graphs
• Independent set in \(P_5\)-free graphs in polynomial time
• Independent sets of maximum weight in apple-free graphs
• Maximum weight independent sets in classes related to claw-free graphs
• Maximum weight independent sets in hole- and dart-free graphs
• Modular decomposition and transitive orientation
• New sufficient conditions for \(\alpha\)-redundant vertices
• 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 easy and hard hereditary classes of graphs with respect to the independent set problem
• On independent vertex sets in subclasses of apple-free graphs
• On maximal independent sets of vertices in claw-free graphs
• On the maximum independent set problem in subclasses of subcubic graphs
• On the stable set problem in special \(P_{5}\)-free graphs
• Some classes of perfectly orderable graphs
• Stability in \(P_5\)- and banner-free graphs
• Stable sets in two subclasses of banner-free graphs
• The Maximum Independent Set Problem in Planar Graphs
• The complexity of generalized clique packing
• The ellipsoid method and its consequences in combinatorial optimization
• The maximum independent set problem in subclasses of subcubic graphs
• Vertex disjoint paths for dispatching in railways
• Weighted efficient domination in two subclasses of P₆-free graphs
• Weighted independent sets in classes of \(P_6\)-free graphs

Cited in

(12)

• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs
• The maximum weight stable set problem in (\(P_6\), bull)-free graphs
• Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs
• Algorithm to find a maximum 2-packing set in a cactus
• Weighted independent sets in classes of \(P_6\)-free graphs
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• Structure of squares and efficient domination in graph classes
• Maximum weight independent sets in (P₆, co-banner)-free graphs
• The exact weighted independent set problem in perfect graphs and related classes
• Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
• Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
• Independent Sets in Classes Related to Chair-Free Graphs

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

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