A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios

DOI10.1016/S0377-2217(96)00271-8zbMath0919.90140OpenAlexW2075128465MaRDI QIDQ1278660

Marc Demange, Vangelis Th. Paschos

Publication date: 22 February 1999

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-2217(96)00271-8

zbMATH Keywords

heuristicspolynomial time algorithmmaximum independent set problemKönig-Egervary graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

When is \(G^2\) a König-Egerváry graph? ⋮ Two more characterizations of König-Egerváry graphs ⋮ Critical independent sets and König-Egerváry graphs ⋮ A classification of 1-well-covered graphs ⋮ On maximum matchings in König-Egerváry graphs ⋮ Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids ⋮ A characterization of Konig-Egervary graphs using a common property of all maximum matchings ⋮ On \(\alpha\)-critical edges in König--Egerváry graphs ⋮ Finding clique clusters with the highest betweenness centrality ⋮ On Duality between Local Maximum Stable Sets of a Graph and Its Line-Graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient bounds for the stable set, vertex cover and set packing problems
• Three short proofs in graph theory
• Independence numbers of graphs - an extension of the Koenig-Egervary theorem
• The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems
• Node-weighted graphs having the König-Egerváry property
• Vertex packings: Structural properties and algorithms