On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem
From MaRDI portal
Publication:385962
DOI10.1016/j.tcs.2013.11.019zbMath1278.05232MaRDI QIDQ385962
Publication date: 13 December 2013
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2013.11.019
graph algorithms; modular decomposition; \(P_5\)-free graphs; clique separators; maximum weight independent set problem
05C75: Structural characterization of families of graphs
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C51: Graph designs and isomorphic decomposition
Related Items
Combining decomposition approaches for the maximum weight stable set problem, Weighted independent sets in classes of \(P_6\)-free graphs, Maximum weight independent sets in classes related to claw-free graphs, Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs, Weighted independent sets in a subclass of \(P_6\)-free graphs, Independent sets in some classes of \(S_{i,j,k}\)-free graphs, More results on weighted independent domination, Independent Sets in Classes Related to Chair-Free Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Maximum weight independent sets in hole- and dart-free graphs
- Maximum weight independent sets in hole- and co-chair-free graphs
- New graph classes of bounded clique-width
- On algorithms for (\(P_5\), gem)-free graphs
- On independent vertex sets in subclasses of apple-free graphs
- New applications of clique separator decomposition for the maximum weight stable set problem
- 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
- Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
- On variations of \(P_{4}\)-sparse graphs
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- (\(P_{5}\), diamond)-free graphs revisited: Structure and linear time optimization.
- On the stable set problem in special \(P_{5}\)-free graphs
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Vertex Disjoint Paths for Dispatching in Railways.
- P4-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
- Data Mining with optimized two-dimensional association rules
- A Linear Recognition Algorithm for Cographs
- Graph Classes: A Survey
- 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
