Exploiting Reduction Rules and Data Structures: Local Search for Minimum Vertex Cover in Massive Graphs
The Minimum Vertex Cover (MinVC) problem is a well-known NP-hard problem. Recently there has been great interest in solving this problem on real-world massive graphs. For such graphs, local search is a promising approach to finding optimal or near-optimal solutions. In this paper we propose a local search algorithm that exploits reduction rules and data structures to solve the MinVC problem in such graphs. Experimental results on a wide range of real-word massive graphs show that our algorithm finds better covers than state-of-the-art local search algorithms for MinVC. Also we present interesting results about the complexities of some well-known heuristics.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Exact yet Efficient Graph Parsing, Bi-directional Locality and the Constructivist Hypothesis
A key problem in processing graph-based meaning representations is graph parsing, i.e. computing all possible derivations of a given graph according to a (competence) grammar. We demonstrate, for the first time, that exa…
Language-Preserving Reduction Rules for Block-Structured Workflow Nets
Process models are used by human analysts to model and analyse behaviour, and by machines to verify properties such as soundness, liveness or other reachability properties, and to compare their expressed behaviour with r…
Why do similarity matching objectives lead to Hebbian/anti-Hebbian networks?
Modeling self-organization of neural networks for unsupervised learning using Hebbian and anti-Hebbian plasticity has a long history in neuroscience. Yet, derivations of single-layer networks with such local learning rul…
Dimensionality ReductionPhysics-guided surrogate learning enables zero-shot control of turbulent wings
Turbulent boundary layers over aerodynamic surfaces are a major source of aircraft drag, yet their control remains challenging due to multiscale dynamics and spatial variability, particularly under adverse pressure gradi…
Reinforcement LearningScreening Rules and its Complexity for Active Set Identification
Screening rules were recently introduced as a technique for explicitly identifying active structures such as sparsity, in optimization problem arising in machine learning. This has led to new methods of acceleration base…
BIG-bench Machine LearningDimensionality Reduction