Maximum weight independent sets in hole- and dart-free graphs

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

zbMATH Keywords

graph algorithms; clique separators; maximum weight independent set problem; hole-free graphs; dart-free greaphs; gem-free graphs

Mathematics Subject Classification ID

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