A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
From MaRDI portal
Publication:1278660
DOI10.1016/S0377-2217(96)00271-8zbMath0919.90140MaRDI QIDQ1278660
Vangelis Th. Paschos, Marc Demange
Publication date: 22 February 1999
Published in: European Journal of Operational Research (Search for Journal in Brave)
90C35: Programming involving graphs or networks
Related Items
Triangle-free graphs with uniquely restricted maximum matchings and their corresponding greedoids, On \(\alpha\)-critical edges in König--Egerváry graphs, 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