Weighted independent sets in a subclass of \(P_6\)-free graphs
From MaRDI portal
Publication:906493
DOI10.1016/j.disc.2015.12.008zbMath1329.05140arXiv1504.05401OpenAlexW2963527469MaRDI QIDQ906493
Publication date: 21 January 2016
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1504.05401
Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)
Related Items (8)
Weighted independent sets in classes of \(P_6\)-free graphs ⋮ The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs ⋮ Structure of squares and efficient domination in graph classes ⋮ Maximum weight independent sets for (\(P_7\),triangle)-free graphs in polynomial time ⋮ Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs ⋮ Algorithm to find a maximum 2-packing set in a cactus ⋮ Independent Sets in Classes Related to Chair-Free Graphs ⋮ Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Weighted independent sets in classes of \(P_6\)-free graphs
- Maximum weight independent sets in classes related to claw-free graphs
- On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
- Maximum weight independent sets in hole- and dart-free graphs
- Graphs without large apples and the maximum weight independent set problem
- On independent vertex sets in subclasses of apple-free graphs
- Weighted efficient domination in two subclasses of \(P_6\)-free graphs
- 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
- Computing independent sets in graphs with large girth
- Modular decomposition and transitive orientation
- On easy and hard hereditary classes of graphs with respect to the independent set problem
- Stable sets in two subclasses of banner-free graphs
- Stability in \(P_5\)- and banner-free graphs
- On the stable set problem in special \(P_{5}\)-free 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
- Vertex Disjoint Paths for Dispatching in Railways.
- Data Mining with optimized two-dimensional association rules
- The Maximum Independent Set Problem in Planar Graphs
- A Linear Recognition Algorithm for Cographs
- Some classes of perfectly orderable graphs
- Graph Classes: A Survey
- Independence and Efficient Domination on P6-free Graphs
- Independent Set in P5-Free Graphs in Polynomial Time
- 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: Weighted independent sets in a subclass of \(P_6\)-free graphs