Computing maximum stable sets for distance-hereditary graphs

DOI10.1016/j.disopt.2005.03.004zbMath1135.05312OpenAlexW2013491634MaRDI QIDQ2568337

Éric Thierry, Olivier Cogis

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

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

Related Items

Hamilton cycles in almost distance-hereditary graphs, The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes, A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion, Simple linear-time algorithms for counting independent sets in distance-hereditary graphs, A parity domination problem in graphs with bounded treewidth and distance-hereditary graphs, The generalized independent set problem: polyhedral analysis and solution approaches, Unnamed Item, Fast and simple algorithms for counting dominating sets in distance-hereditary graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completely separable graphs
• Distance-hereditary graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Graph Classes: A Survey
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs