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

DOI10.1016/j.disc.2015.12.008zbMath1329.05140arXiv1504.05401MaRDI QIDQ906493

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 algorithms; independent sets; \(P_6\)-free graphs

Mathematics Subject Classification ID

05C85: Graph algorithms (graph-theoretic aspects)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)

05C22: Signed and weighted graphs

Related Items

Weighted independent sets in classes of \(P_6\)-free graphs, Structure of squares and efficient domination in graph classes, 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, Algorithm to find a maximum 2-packing set in a cactus, Independent Sets in Classes Related to Chair-Free Graphs, Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs, The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Weighted independent sets in classes of \(P_6\)-free graphs
• 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
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Maximum weight independent sets in hole- and dart-free graphs
• Graphs without large apples and the maximum weight independent set problem
• On independent vertex sets in subclasses of apple-free graphs
• Weighted efficient domination in two subclasses of \(P_6\)-free graphs
• Decomposition by clique separators
• The complexity of generalized clique packing
• 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
• Computing independent sets in graphs with large girth
• Modular decomposition and transitive orientation
• 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
• On the stable set problem in special \(P_{5}\)-free graphs
• On the maximum independent set problem in subclasses of subcubic graphs
• New sufficient conditions for \(\alpha\)-redundant vertices
• The maximum independent set problem in subclasses of subcubic 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
• The Maximum Independent Set Problem in Planar Graphs
• A Linear Recognition Algorithm for Cographs
• Some classes of perfectly orderable graphs
• Graph Classes: A Survey
• Independence and Efficient Domination on P₆-free Graphs
• Independent Set in P₅-Free Graphs in Polynomial Time
• 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