Computing maximum stable sets for distance-hereditary graphs

DOI10.1016/J.DISOPT.2005.03.004zbMATH Open1135.05312OpenAlexW2013491634MaRDI QIDQ2568337FDOQ2568337

Authors: Olivier Cogis, Eric Thierry 

Publication date: 10 October 2005

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2005.03.004

Recommendations

• Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
• An exact algorithm for the maximum stable set problem
• Minimum degree algorithms for stability number
• Polynomially solvable cases for the maximum stable set problem
• The path-partition problem in bipartite distance-hereditary graphs

zbMATH Keywords

Combinatorial optimizationDistance-hereditary graphGreedy scheme

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Distance in graphs (05C12) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Graph Classes: A Survey
• Linear time solvable optimization problems on graphs of bounded clique-width
• Distance-hereditary graphs
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Title not available (Why is that?)
• Completely separable graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (10)

• Fast and simple algorithms for counting dominating sets in distance-hereditary graphs
• The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
• Minimum degree algorithms for stability number
• Hamilton cycles in almost distance-hereditary graphs
• Title not available (Why is that?)
• A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion
• A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs
• Simple linear-time algorithms for counting independent sets in distance-hereditary graphs
• The generalized independent set problem: polyhedral analysis and solution approaches
• Title not available (Why is that?)

This page was built for publication: Computing maximum stable sets for distance-hereditary graphs

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