Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs

DOI10.1007/978-3-319-42634-1_31zbMath1476.68210OpenAlexW2499511520MaRDI QIDQ2817880

Frédéric Maffray, T. Karthick

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-42634-1_31

zbMATH Keywords

claw-free graphgraph algorithmsmodular decompositionweighted independent setbull-free graphfork-free graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (3)

Independent sets in some classes of \(S_{i,j,k}\)-free graphs ⋮ Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs ⋮ Polynomial cases for the vertex coloring problem

Cites Work

• Unnamed Item
• Maximum weight independent sets in classes related to claw-free graphs
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• A polynomial Turing-kernel for weighted independent set in bull-free graphs
• Maximum weight independent sets in hole- and dart-free graphs
• Graphs without large apples and the maximum weight independent set problem
• The structure of bull-free graphs I -- three-edge-paths with centers and anticenters
• The structure of bull-free graphs II and III -- a summary
• Weighted independent sets in a subclass of \(P_6\)-free graphs
• Weighted efficient domination in two subclasses of \(P_6\)-free graphs
• 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
• Stable sets in two subclasses of banner-free graphs
• Recognizing bull-free perfect 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
• The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs
• The Maximum Independent Set Problem in Planar Graphs
• A Linear Recognition Algorithm for Cographs
• Graph Classes: A Survey
• Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
• Computational Complexity
• 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: Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs