Local search with edge weighting and configuration checking heuristics for minimum vertex cover
From MaRDI portal
Publication:646517
DOI10.1016/J.ARTINT.2011.03.003zbMATH Open1225.68242OpenAlexW2038777942MaRDI QIDQ646517FDOQ646517
Authors: Shaowei Cai, Kaile Su, Abdul Sattar 
Publication date: 17 November 2011
Published in: Artificial Intelligence (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/10072/40810
Recommendations
- NuMVC: an efficient local search algorithm for minimum vertex cover
- Combining edge weight and vertex weight for minimum vertex cover problem
- An efficient local search framework for the minimum weighted vertex cover problem
- Towards faster local search for minimum weight vertex cover on massive graphs
- Finding a small vertex cover in massive sparse graphs: construct, local search, and preprocess
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Combinatorial optimization (90C27)
Cites Work
- Title not available (Why is that?)
- Tabu Search—Part I
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Approximating Maximum Clique by Removing Subgraphs
- Title not available (Why is that?)
- Some optimal inapproximability results
- On the hardness of approximating minimum vertex cover
- A fast algorithm for the maximum clique problem
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers
- Handbook of knowledge representation.
- Stochastic local search. Foundations and applications.
- Tabu Search—Part II
- Title not available (Why is that?)
- Reactive local search for the maximum clique problem
- An ant colony optimization algorithm for the minimum weight vertex cover problem
- An exact algorithm for the maximum clique problem
- Random constraint satisfaction: easy generation of hard (satisfiable) instances
- Many hard examples in exact phase transitions
- Title not available (Why is that?)
- Towards a characterisation of the behaviour of stochastic local search algorithms for SAT
- Phased local search for the maximum clique problem
- A study of ACO capabilities for solving the maximum clique problem
- Title not available (Why is that?)
- Title not available (Why is that?)
- Simple ingredients leading to very efficient heuristics for the maximum clique problem
- 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
- Optimized Crossover for the Independent Set Problem
- Local search: is brute-force avoidable?
- Local search algorithms for SAT: an empirical evaluation
- Theory and Applications of Satisfiability Testing
- Using constraint programming to solve the maximum clique problem
- Automata, Languages and Programming
- Theory and Applications of Satisfiability Testing
- Erratum: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
- Clause weighting local search for SAT
Cited In (39)
- Solving the set packing problem via a maximum weighted independent set heuristic
- An iterative path-breaking approach with mutation and restart strategies for the MAX-SAT problem
- SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem
- A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets
- Title not available (Why is that?)
- Fairer comparisons for travelling salesman problem solutions using hash functions
- Monte Carlo tree search with adaptive simulation: a case study on weighted vertex coloring
- Analysis of an iterated local search algorithm for vertex cover in sparse random graphs
- Finding a small vertex cover in massive sparse graphs: construct, local search, and preprocess
- Local Search for Minimum Weight Dominating Set with Two-Level Configuration Checking and Frequency Based Scoring Function
- On the parameterized vertex cover problem for graphs with perfect matching
- An efficient local search framework for the minimum weighted vertex cover problem
- Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers
- Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains
- A vertex weighting-based double-tabu search algorithm for the classical \(p\)-center problem
- Combining edge weight and vertex weight for minimum vertex cover problem
- A novel local search algorithm with configuration checking and scoring mechanism for the set k‐covering problem
- New local search methods for partial MaxSAT
- New stochastic local search approaches for computing preferred extensions of abstract argumentation
- Towards faster local search for minimum weight vertex cover on massive graphs
- Local Search For Satisfiability Modulo Integer Arithmetic Theories
- Local search for Boolean satisfiability with configuration checking and subscore
- An efficient local search algorithm for solving maximum edge weight clique problem in large graphs
- The solution space structure of planted constraint satisfaction problems with growing domains
- Multi-neighborhood tabu search for the maximum weight clique problem
- Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism
- Local search for diversified top-\(k\) clique search problem
- An improved configuration checking-based algorithm for the unicost set covering problem
- Backdoors to tractable answer set programming
- Incremental Upper Bound for the Maximum Clique Problem
- \textsc{ahmaxsat}: description and evaluation of a branch and bound Max-SAT solver
- Improving configuration checking for satisfiable random \(k\)-SAT instances
- A review on algorithms for maximum clique problems
- NuMVC: an efficient local search algorithm for minimum vertex cover
- On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem
- Complete Boolean satisfiability solving algorithms based on local search
- MLQCC: an improved local search algorithm for the set k‐covering problem
- An efficient heuristic algorithm for solving connected vertex cover problem
- CCAnr: a configuration checking based local search solver for non-random satisfiability
Uses Software
This page was built for publication: Local search with edge weighting and configuration checking heuristics for minimum vertex cover
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q646517)
