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.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
Related Items (10)
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
This page was built for publication: A generalization of König-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios
