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

DOI10.1016/J.DAM.2012.06.015MaRDI QIDQ714022zbMATH OpenOpenAlexFDO

Authors L. Sunil Chandran, T. Karthick, 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 algorithmsclique separatorsmaximum weight independent set problemhole-free graphsdart-free greaphsgem-free graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Signed and weighted graphs (05C22)

Recommendations

• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• Maximum weight independent sets in hole- and co-chair-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
• Maximum weight independent sets for (\(S_{1,2,4}\), triangle)-free graphs in polynomial time

Cites work

• scientific article; zbMATH DE number 3908479 (Why is no real title available?)
• scientific article; zbMATH DE number 3513839 (Why is no real title available?)
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Decomposition by clique separators
• Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
• Finding large holes
• Four classes of perfectly orderable graphs
• Independent sets of maximum weight in apple-free graphs
• Maximum weight independent sets in hole- and co-chair-free graphs
• New applications of clique separator decomposition for the maximum weight stable set problem
• On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
• On the stable set problem in special \(P_{5}\)-free graphs
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• The complexity of generalized clique packing
• The ellipsoid method and its consequences in combinatorial optimization
• The strong perfect graph theorem

Cited in

(17)

• Maximum weight independent sets in hole- and co-chair-free graphs
• On the maximum weight independent set problem in graphs without induced cycles of length at least five
• Graphs without large apples and the maximum weight independent set problem
• scientific article; zbMATH DE number 1617260 (Why is no real title available?)
• Maximum weighted independent sets on transitive graphs and applications
• 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
• Complexity and polynomially solvable special cases of QUBO
• Maximum Weight Independent Sets in ( $$S_{1,1,3}$$ , bull)-free Graphs
• One-three join: a graph operation and its consequences
• Weighted independent sets in a subclass of P₆-free graphs
• Structure of squares and efficient domination in graph classes
• Addendum to: ``Maximum weight independent sets in hole- and co-chair-free graphs
• Maximum weight independent sets in odd-hole-free graphs without dart or without bull
• Independent Sets in Classes Related to Chair-Free Graphs
• Induced subgraphs of bounded treewidth and the container method

This page was built for publication: Maximum weight independent sets in hole- and dart-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714022)