Finding near-optimal independent sets at scale

DOI10.1007/s10732-017-9337-xzbMath1370.90222arXiv1509.00764OpenAlexW2962800229MaRDI QIDQ2401330

Sebastian Lamm, Darren Strash, Peter Sanders, Renato F. Werneck, Christian Schulz

Publication date: 8 September 2017

Published in: Journal of Heuristics, 2016 Proceedings of the Eighteenth Workshop on Algorithm Engineering and Experiments (ALENEX) (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1509.00764

zbMATH Keywords

local searchheuristic algorithmsmaximum independent set problemkernelizationevolutionary/genetic algorithmsminimum vertex cover problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Reducing graph coloring to clique search, Finding near-optimal independent sets at scale, Reinforcement learning for combinatorial optimization: a survey, A fast approximation algorithm for the maximum 2-packing set problem on planar graphs, Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket, A genetic algorithm for the maximum 2-packing set problem

Uses Software

• SparseMatrix
• DIMACS
• WebGraph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast local search for the maximum independent set problem
• Exact exponential algorithms.
• Variable neighborhood search for the maximum clique
• An exact bit-parallel algorithm for the maximum clique problem
• Branch-and-reduce exponential/FPT algorithms in practice: a case study of vertex cover
• Simple ingredients leading to very efficient heuristics for the maximum clique problem
• An effective local search for the maximum clique problem
• A combined evolutionary search and multilevel optimisation approach to graph-partitioning
• Confining sets and avoiding bottleneck cases: a simple maximum independent set algorithm in degree-3 graphs
• An improved bit parallel exact maximum clique algorithm
• Finding near-optimal independent sets at scale
• Fast algorithms for max independent set
• Improvements to MCS algorithm for the maximum clique problem
• Using critical sets to solve the maximum independent set problem
• A review on algorithms for maximum clique problems
• Exact Algorithms for Maximum Independent Set
• The university of Florida sparse matrix collection
• A Simple and Faster Branch-and-Bound Algorithm for Finding a Maximum Clique
• Engineering Route Planning Algorithms
• Vertex packings: Structural properties and algorithms
• Finding a Maximum Independent Set
• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• Evaluation of Labeling Strategies for Rotating Maps
• Linear-Time FPT Algorithms via Network Flow
• Reactive local search for the maximum clique problem