Fast local search for the maximum independent set problem
From MaRDI portal
Publication:519101
DOI10.1007/s10732-012-9196-4zbMath1358.90143OpenAlexW2098667053MaRDI QIDQ519101
Diogo V. Andrade, Mauricio G. C. Resende, Renato F. Werneck
Publication date: 4 April 2017
Published in: Journal of Heuristics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10732-012-9196-4
Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
A review on algorithms for maximum clique problems, A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs, A new exact maximum clique algorithm for large and massive sparse graphs, Finding near-optimal independent sets at scale, The weighted independent domination problem: integer linear programming models and metaheuristic approaches, An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem†, Maximum independent sets and supervised learning, Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket, Efficient Algorithms for Finding Maximum and Maximal Cliques and Their Applications, Improvements to MCS algorithm for the maximum clique problem, A hybrid iterated local search heuristic for the maximum weight independent set problem, Speeding up branch and bound algorithms for solving the maximum clique problem, Iterated local search with Trellis-neighborhood for the partial Latin square extension problem, A genetic algorithm for the maximum 2-packing set problem, Conflict resolving -- a local search algorithm for solving large scale conflict graphs in freight railway timetabling, Incremental optimization of independent sets under the reconfiguration framework, On the Power of Simple Reductions for the Maximum Independent Set Problem, Speeding up MCS Algorithm for the Maximum Clique Problem with ILS Heuristic and Other Enhancements, An enhanced bitstring encoding for exact maximum clique search in sparse graphs, An Efficient Local Search for the Minimum Independent Dominating Set Problem
Uses Software
Cites Work
- Variable neighborhood search for the maximum clique
- Simple ingredients leading to very efficient heuristics for the maximum clique problem
- An effective local search for the maximum clique problem
- A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
- Reducibility among Combinatorial Problems
- Reactive local search for the maximum clique problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
