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

DOI10.1007/978-3-319-42634-1_31MaRDI QIDQ2817880zbMATH OpenOpenAlexFDO

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

graph algorithms modular decomposition claw-free graph weighted independent set bull-free graph fork-free graph

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)

Recommendations

Maximum weight independent sets in odd-hole-free graphs without dart or without bull
Maximum weight stable set in ($P_7$, bull)-free graphs and ($S_{1, 2, 3}$, bull)-free graphs
Maximum weight independent sets for ($S_{1,2,4}$, triangle)-free graphs in polynomial time
Maximum weight independent sets in hole- and co-chair-free graphs
Maximum weight independent sets in hole- and dart-free graphs
Maximum weight independent sets in classes related to claw-free graphs
Maximum weight independent sets in (P₆, co-banner)-free graphs
The maximum weight stable set problem in ($P_6$, bull)-free graphs
Independent sets of maximum weight in ($p,q$)-colorable graphs.
Independent sets of maximum weight in apple-free graphs

Cites work

scientific article; zbMATH DE number 3445275 (Why is no real title available?)
A Linear Recognition Algorithm for Cographs
A polynomial Turing-kernel for weighted independent set in bull-free graphs
A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
Computational Complexity
Graph Classes: A Survey
Graphs without large apples and the maximum weight independent set problem
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
Maximum weight independent sets in odd-hole-free graphs without dart or without bull
New sufficient conditions for $\alpha$-redundant vertices
On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
On diameters and radii of bridged graphs
On maximal independent sets of vertices in claw-free graphs
On the maximum independent set problem in subclasses of subcubic graphs
Recognizing bull-free perfect 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
The maximum weight stable set problem in ($P_6$, bull)-free graphs
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 efficient domination in two subclasses of P₆-free graphs
Weighted independent sets in a subclass of P₆-free graphs

Cited in

(7)

Independent sets in some classes of $S_{i,j,k}$-free graphs
Improved FPT algorithms for weighted independent set in bull-free graphs
Maximum weight independent sets in classes related to claw-free graphs
Maximum weight independent sets for ($S_{1,2,4}$, triangle)-free graphs in polynomial time
Maximum weight independent sets in odd-hole-free graphs without dart or without bull
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

This page was built for publication: Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs

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