On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem

DOI10.1016/j.tcs.2013.11.019zbMath1278.05232OpenAlexW2013909012MaRDI QIDQ385962

T. Karthick

Publication date: 13 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.11.019

zbMATH Keywords

graph algorithmsmodular decomposition\(P_5\)-free graphsclique separatorsmaximum weight independent set problem

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph designs and isomorphic decomposition (05C51)

Related Items (8)

Weighted independent sets in classes of \(P_6\)-free graphs ⋮ Maximum weight independent sets in classes related to claw-free graphs ⋮ Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ More results on weighted independent domination ⋮ Combining decomposition approaches for the maximum weight stable set problem ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs ⋮ Independent Sets in Classes Related to Chair-Free Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Maximum weight independent sets in hole- and dart-free graphs
• Maximum weight independent sets in hole- and co-chair-free graphs
• New graph classes of bounded clique-width
• On algorithms for (\(P_5\), gem)-free graphs
• On independent vertex sets in subclasses of apple-free graphs
• New applications of clique separator decomposition for the maximum weight stable set problem
• 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
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• On variations of \(P_{4}\)-sparse graphs
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
• On the stable set problem in special \(P_{5}\)-free graphs
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• Vertex Disjoint Paths for Dispatching in Railways.
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• Data Mining with optimized two-dimensional association rules
• A Linear Recognition Algorithm for Cographs
• Graph Classes: A Survey
• 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: On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem