Computing maximum stable sets for distance-hereditary graphs

DOI10.1016/J.DISOPT.2005.03.004MaRDI QIDQ2568337zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Combinatorial optimizationDistance-hereditary graphGreedy scheme

Mathematics Subject Classification ID

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

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

Cites work

• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
• Completely separable graphs
• Distance-hereditary graphs
• Graph Classes: A Survey
• scientific article; zbMATH DE number 1303031 (Why is no real title available?)
• scientific article; zbMATH DE number 2044928 (Why is no real title available?)
• scientific article; zbMATH DE number 1500541 (Why is no real title available?)
• scientific article; zbMATH DE number 815104 (Why is no real title available?)
• scientific article; zbMATH DE number 1420904 (Why is no real title available?)
• Linear time solvable optimization problems on graphs of bounded clique-width

Cited in

(11)

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

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)