Local search with edge weighting and configuration checking heuristics for minimum vertex cover
From MaRDI portal
Publication:646517
DOI10.1016/j.artint.2011.03.003zbMath1225.68242OpenAlexW2038777942MaRDI QIDQ646517
Kaile Su, Shaowei Cai, 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
Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items (31)
Solving the set packing problem via a maximum weighted independent set heuristic ⋮ A review on algorithms for maximum clique problems ⋮ CCAnr: A Configuration Checking Based Local Search Solver for Non-random Satisfiability ⋮ New local search methods for partial MaxSAT ⋮ The solution space structure of planted constraint satisfaction problems with growing domains ⋮ On minimization of the number of branches in branch-and-bound algorithms for the maximum clique problem ⋮ A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets ⋮ An efficient local search algorithm for solving maximum edge weight clique problem in large graphs ⋮ A vertex weighting-based double-tabu search algorithm for the classical \(p\)-center problem ⋮ On the parameterized vertex cover problem for graphs with perfect matching ⋮ Local Search For Satisfiability Modulo Integer Arithmetic Theories ⋮ MLQCC: an improved local search algorithm for the set k‐covering problem ⋮ Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism ⋮ Fairer comparisons for travelling salesman problem solutions using hash functions ⋮ Monte Carlo tree search with adaptive simulation: a case study on weighted vertex coloring ⋮ Towards faster local search for minimum weight vertex cover on massive graphs ⋮ Complete Boolean satisfiability solving algorithms based on local search ⋮ Incremental Upper Bound for the Maximum Clique Problem ⋮ An efficient heuristic algorithm for solving connected vertex cover problem ⋮ An iterative path-breaking approach with mutation and restart strategies for the MAX-SAT problem ⋮ New stochastic local search approaches for computing preferred extensions of abstract argumentation ⋮ Local search for Boolean satisfiability with configuration checking and subscore ⋮ An improved configuration checking-based algorithm for the unicost set covering problem ⋮ Improving configuration checking for satisfiable random \(k\)-SAT instances ⋮ Multi-neighborhood tabu search for the maximum weight clique problem ⋮ An efficient local search framework for the minimum weighted vertex cover problem ⋮ Local search for diversified top-\(k\) clique search problem ⋮ SCCWalk: an efficient local search algorithm and its improvements for maximum weight clique problem ⋮ Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains ⋮ Backdoors to tractable answer set programming ⋮ ahmaxsat: Description and Evaluation of a Branch and Bound Max-SAT Solver
Uses Software
Cites Work
- Local search: is brute-force avoidable?
- An ant colony optimization algorithm for the minimum weight vertex cover problem
- On the hardness of approximating minimum vertex cover
- Erratum: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments
- Clause weighting local search for SAT
- An exact algorithm for the maximum clique problem
- Simple ingredients leading to very efficient heuristics for the maximum clique problem
- Optimisation of unweighted/weighted maximum independent sets and minimum vertex covers
- Random constraint satisfaction: easy generation of hard (satisfiable) instances
- Local search algorithms for SAT: an empirical evaluation
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Towards a characterisation of the behaviour of stochastic local search algorithms for SAT
- A heuristic for the maximum independent set problem based on optimization of a quadratic over a sphere
- A fast algorithm for the maximum clique problem
- A novel evolutionary formulation of the maximum independent set problem
- Many hard examples in exact phase transitions
- Phased local search for the maximum clique problem
- A study of ACO capabilities for solving the maximum clique problem
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Tabu Search—Part I
- Tabu Search—Part II
- Optimized Crossover for the Independent Set Problem
- Approximating Maximum Clique by Removing Subgraphs
- Some optimal inapproximability results
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
- Automata, Languages and Programming
- Principles and Practice of Constraint Programming – CP 2003
- Reactive local search for the maximum clique problem
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Local search with edge weighting and configuration checking heuristics for minimum vertex cover
