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.68242MaRDI 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
90C27: Combinatorial optimization
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Related Items
Belief propagation guided decimation algorithms for random constraint satisfaction problems with growing domains, ahmaxsat: Description and Evaluation of a Branch and Bound Max-SAT Solver, The solution space structure of planted constraint satisfaction problems with growing domains, A Fast Vertex Weighting-Based Local Search for Finding Minimum Connected Dominating Sets, Incremental Upper Bound for the Maximum Clique Problem, New stochastic local search approaches for computing preferred extensions of abstract argumentation, A vertex weighting-based double-tabu search algorithm for the classical \(p\)-center problem, Local Search For Satisfiability Modulo Integer Arithmetic Theories, MLQCC: an improved local search algorithm for the set k‐covering problem, New local search methods for partial MaxSAT, Local search for Boolean satisfiability with configuration checking and subscore, Improving configuration checking for satisfiable random \(k\)-SAT instances, Solving the set packing problem via a maximum weighted independent set heuristic, On the parameterized vertex cover problem for graphs with perfect matching, On minimization of the number of branches in branch-and-bound algorithms 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, Multi-neighborhood tabu search for the maximum weight clique problem, An efficient local search algorithm for solving maximum edge weight clique problem in large graphs, Towards faster local search for minimum weight vertex cover on massive graphs, An improved configuration checking-based algorithm for the unicost set covering 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, Backdoors to tractable answer set programming, Complete Boolean satisfiability solving algorithms based on local search, A review on algorithms for maximum clique problems, Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism, CCAnr: A Configuration Checking Based Local Search Solver for Non-random Satisfiability
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
