A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem

DOI10.1016/0960-0779(94)00175-PzbMath0903.68097OpenAlexW2048720727MaRDI QIDQ1129388

Mohamed Afif, Vangelis Th. Paschos, Aristidis Likas

Publication date: 16 August 1998

Published in: Chaos, Solitons and Fractals (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0960-0779(94)00175-p

zbMATH Keywords

parallel algorithmminimum set covering problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A parallel algorithm for the minimum weighted vertex cover problem
• Efficient bounds for the stable set, vertex cover and set packing problems
• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
• Improved approximations for maximum independent set via approximation chains

This page was built for publication: A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem