Weighted independent sets in classes of P₆-free graphs
DOI10.1016/J.DAM.2015.10.015zbMATH Open1339.05170OpenAlexW2190717998MaRDI QIDQ298979FDOQ298979
Publication date: 21 June 2016
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2015.10.015
Recommendations
- Weighted independent sets in a subclass of \(P_6\)-free graphs
- Independent Sets in Classes Related to Chair-Free Graphs
- Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
- Maximum weight independent sets in classes related to claw-free graphs
- Maximum weight independent sets for (\(P_7\), triangle)-free graphs in polynomial time
graph algorithmsmodular decompositionclaw-free graph\(P_6\)-free graphclique separatorweighted independent set
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)
Cites Work
- Title not available (Why is that?)
- Graph Classes: A Survey
- Decomposition by clique separators
- The ellipsoid method and its consequences in combinatorial optimization
- Modular decomposition and transitive orientation
- Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
- Some results on graphs without long induced paths
- On maximal independent sets of vertices in claw-free graphs
- On diameters and radii of bridged graphs
- A charming class of perfectly orderable graphs
- Stable sets in certain \(P_6\)-free graphs
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- Stable sets in two subclasses of banner-free graphs
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- Maximum weight independent sets in (\(P_6\), co-banner)-free graphs
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Vertex disjoint paths for dispatching in railways
- Maximum weight independent sets in classes related to claw-free graphs
- Data Mining with optimized two-dimensional association rules
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Linear Recognition Algorithm for Cographs
- 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
- Independence and Efficient Domination on P6-free Graphs
- Title not available (Why is that?)
- 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
- Meyniel weakly triangulated graphs. I: Co-perfect orderability
- Maximum weight independent sets in hole- and dart-free graphs
- New graph classes of bounded clique-width
- On algorithms for (\(P_5\), gem)-free graphs
- New applications of clique separator decomposition for the maximum weight stable set problem
- Weighted independent sets in a subclass of \(P_6\)-free graphs
Cited In (10)
- Polynomial-time Algorithm for Maximum Weight Independent Set on P 6 -free Graphs
- Independent sets in some classes of \(S_{i,j,k}\)-free graphs
- Title not available (Why is that?)
- Weighted independent sets in a subclass of \(P_6\)-free graphs
- The Maximum Weight Stable Set Problem in ( $$P_6$$ , bull)-Free Graphs
- Vizing bound for the chromatic number on some graph classes
- The exact weighted independent set problem in perfect graphs and related classes
- New Cases of the Polynomial Solvability of the Independent Set Problem for Graphs with Forbidden Paths
- Maximum weight stable set in (\(P_7\), bull)-free graphs and (\(S_{1, 2, 3}\), bull)-free graphs
- Independent Sets in Classes Related to Chair-Free Graphs
This page was built for publication: Weighted independent sets in classes of \(P_6\)-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q298979)
