Complexity results for equistable graphs and related classes

DOI10.1007/s10479-010-0720-3zbMath1225.90148OpenAlexW2127494080WikidataQ59592308 ScholiaQ59592308MaRDI QIDQ646721

Martin Milanič, Gábor Rudolf, James B. Orlin

Publication date: 17 November 2011

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/77910

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Dynamic programming (90C39)

Related Items (7)

Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs ⋮ Equistable simplicial, very well-covered, and line graphs ⋮ Total domishold graphs: a generalization of threshold graphs, with connections to threshold hypergraphs ⋮ Short proofs on the structure of general partition, equistable and triangle graphs ⋮ Linear separation of connected dominating sets in graphs ⋮ Recognizing k-equistable Graphs in FPT Time ⋮ Strong cliques and equistability of EPT graphs

Cites Work

• Unnamed Item
• A class of threshold and domishold graphs: Equistable and equidominating graphs
• New applications of clique separator decomposition for the maximum weight stable set problem
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
• Equistable series-parallel graphs
• Equistable chordal graphs
• Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.
• Threshold graphs and related topics
• Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs
• Equistable distance-hereditary graphs
• Equistable graphs
• Independent Sets of Maximum Weight in Apple-Free Graphs
• A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

This page was built for publication: Complexity results for equistable graphs and related classes