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

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

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 graph; graph algorithms; modular decomposition; weighted independent set; bull-free graph; fork-free graph

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

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

Related Items

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

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