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

DOI10.1007/978-3-319-42634-1_31zbMATH Open1476.68210OpenAlexW2499511520MaRDI QIDQ2817880FDOQ2817880

Authors: T. Karthick, Frédéric Maffray

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

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_6$, 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

zbMATH Keywords

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

Cites Work

Graph Classes: A Survey
Computational Complexity
The ellipsoid method and its consequences in combinatorial optimization
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
On maximal independent sets of vertices in claw-free graphs
The complexity of generalized clique packing
Title not available (Why is that?)
On diameters and radii of bridged graphs
Stable sets in two subclasses of banner-free graphs
Recognizing bull-free perfect graphs
On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
Maximum weight independent sets in classes related to claw-free graphs
A Linear Recognition Algorithm for Cographs
Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
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
Maximum weight independent sets in hole- and dart-free graphs
Weighted independent sets in a subclass of $P_6$-free graphs
The Maximum Independent Set Problem in Planar Graphs
Classes of subcubic planar graphs for which the independent set problem is polynomially solvable
New sufficient conditions for $\alpha$-redundant vertices
Weighted efficient domination in two subclasses of $P_6$-free graphs
Graphs without large apples and the maximum weight independent set problem
On the maximum independent set problem in subclasses of subcubic graphs
The maximum independent set problem in subclasses of subcubic graphs
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
The maximum weight stable set problem in ($P_6$, bull)-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)