Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers

DOI10.1016/j.disopt.2008.12.001zbMath1169.05383OpenAlexW2072210264MaRDI QIDQ1015327

Wayne Pullan

Publication date: 7 May 2009

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2008.12.001

zbMATH Keywords

local searchmaximum weighted independent setminimum weighted vertex cover

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (10)

Subgraph extraction and metaheuristics for the maximum clique problem ⋮ Construction of optimal constant-dimension subspace codes ⋮ An efficient local search algorithm with large neighborhoods for the maximum weighted independent set problem† ⋮ Local search with edge weighting and configuration checking heuristics for minimum vertex cover ⋮ A Semi-exact Algorithm for Quickly Computing A Maximum Weight Clique in Large Sparse Graphs ⋮ New Lower Bounds for Binary Constant-Dimension Subspace Codes ⋮ A hybrid iterated local search heuristic for the maximum weight independent set problem ⋮ The maximum volume hard subset model for Poisson processes: simulation aspects ⋮ An efficient local search framework for the minimum weighted vertex cover problem ⋮ An Efficient Local Search for the Minimum Independent Dominating Set Problem

Uses Software

• QUALEX

Cites Work

• A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
• A novel evolutionary formulation of the maximum independent set problem
• Phased local search for the maximum clique problem
• Optimized Crossover for the Independent Set Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers