Maximum weight independent sets in hole- and dart-free graphs
From MaRDI portal
Publication:714022
DOI10.1016/j.dam.2012.06.015zbMath1252.05211MaRDI QIDQ714022
T. Karthick, L. Sunil Chandran, Manu Basavaraju
Publication date: 19 October 2012
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2012.06.015
graph algorithms; clique separators; maximum weight independent set problem; hole-free graphs; dart-free greaphs; gem-free graphs
05C35: Extremal problems in graph theory
05C85: Graph algorithms (graph-theoretic aspects)
05C22: Signed and weighted graphs
Related Items
Complexity and Polynomially Solvable Special Cases of QUBO, Weighted independent sets in classes of \(P_6\)-free graphs, Structure of squares and efficient domination in graph classes, 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, Maximum weight independent sets in odd-hole-free graphs without dart or without bull, Weighted independent sets in a subclass of \(P_6\)-free graphs, One-three join: a graph operation and its consequences, 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
- Unnamed Item
- Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
- Maximum weight independent sets in hole- and co-chair-free graphs
- The strong perfect graph theorem
- New applications of clique separator decomposition for the maximum weight stable set problem
- Decomposition by clique separators
- The complexity of generalized clique packing
- The ellipsoid method and its consequences in combinatorial optimization
- Finding large holes
- Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
- On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- On the stable set problem in special \(P_{5}\)-free graphs
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Four classes of perfectly orderable graphs
- 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