Implementation of Maximum Weighted Independent Set through Brute Force and Greedy Heuristics Approaches

The optimization problem of the Maximum Weighted Independent Set (MWIS) in graph theory is a significant challenge with wide-ranging applications in resource allocation, network design, and scheduling. This paper introduces algorithmic insights using Greedy Heuristics (GH) and Exhaustive Search (ES) methods for MWIS implementation. Implementations are conducted on graphs with varying weights and sizes (12.5%, 25%, 50%), and evaluation parameters include the number of vertices and edges. The study reveals that GH achieves MWIS outcomes with fewer operations and tests compared to ES, demonstrating its efficiency in solving the MWIS problem. The results suggest that GH is a practical alternative for optimizing large graphs efficiently, balancing solution quality and computational effort. These findings have significant implications for real-world applications requiring quick and effective optimization solutions.