On independent vertex sets in subclasses of apple-free graphs

DOI10.1007/s00453-008-9176-0zbMath1187.05050OpenAlexW1972321305MaRDI QIDQ848838

Raffaele Mosca, Tilo Klembt, Andreas Brandstädt, Vadim V. Lozin

Publication date: 23 February 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-008-9176-0

zbMATH Keywords

efficient algorithmsclique separatorsmaximum weight independent set problemapple-free graphsnearly chordal graphsnearly perfect graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (10)

On atomic structure of \(P_5\)-free subclasses and maximum weight independent set problem ⋮ Combining decomposition approaches for the maximum weight stable set problem ⋮ Set graphs. IV. Further connections with claw-freeness ⋮ Weighted independent sets in a subclass of \(P_6\)-free graphs ⋮ Weighted efficient domination in two subclasses of \(P_6\)-free graphs ⋮ 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 domination in finitely defined classes of graphs: polynomial algorithms ⋮ On distance-3 matchings and induced matchings ⋮ Maximum weight independent sets in hole- and co-chair-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Augmenting graphs for independent sets
• The strong perfect graph theorem
• New applications of clique separator decomposition for the maximum weight stable set problem
• Decomposition by clique separators
• The struction of a graph: Application to CN-free graphs
• The strong perfect graph conjecture for pan-free graphs
• On maximal independent sets of vertices in claw-free graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Modular decomposition and transitive orientation
• Stable sets in certain \(P_6\)-free graphs
• Efficient graph representations
• On linear and circular structure of (claw, net)-free graphs
• Robust algorithms for the stable set problem
• Stable sets in two subclasses of banner-free graphs
• Stability in \(P_5\)- and banner-free graphs
• On the vertex packing problem
• On Hamiltonicity of \{claw, net\}-free graphs
• Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs
• Linear Time Algorithms for Hamiltonian Problems on (Claw,Net)-Free Graphs
• On Clique Separators, Nearly Chordal Graphs, and the Maximum Weight Stable Set Problem
• A Linear Recognition Algorithm for Cographs
• Graph Classes: A Survey
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• A note on \(\alpha\)-redundant vertices in graphs

This page was built for publication: On independent vertex sets in subclasses of apple-free graphs