HSMVS:在巨型图中启发式搜索最小顶点分离器.
1School of Software, Beihang University, Beijing, China.
PeerJ. Computer science
|June 10, 2024
概括
我们开发了HSMVS,这是一个新的启发式搜索算法,用于大图上的最小顶点分离器 (MVS) 问题. 在复杂的图形结构中,HSMVS在寻找较小的顶点分离器方面显著优于现有的方法.
科学领域:
- 图形理论 图形理论
- 计算复杂性 计算复杂性
- 算法设计 算法设计
背景情况:
- 最小顶点分离器 (MVS) 问题是图形理论中的一个基本的NP-hard问题.
- 现实世界的大型图形需要高效的近似方法,特别是启发式搜索算法,因为它们的大规模.
研究的目的:
- 介绍HSMVS,一种新的启发式搜索算法,旨在解决大规模现实世界的图形上的MVS问题.
- 为了证明拟议的HSMVS算法的有效性和效率.
主要方法:
- 根据高效的施工程序开发了HSMVS.
- 在HSMVS算法中整合了一个简单而有效的顶点选择启发式.
主要成果:
- 在许多大规模的现实世界图表上测试了HSMVS.
- 实验结果显示,与三种已建立的启发式搜索算法相比,HSMVS发现的顶点分离器显著较小.
结论:
- 在大型图中,HSMVS算法非常有效地找到最小的顶点分离器.
- 在实际应用中,HSMVS的基本组件有助于其卓越的性能.
相关概念视频
VSEPR Theory and the Basic Shapes
68.2K
Overview of VSEPR Theory
68.2K
Survival Tree
79
Survival trees are a non-parametric method used in survival analysis to model the relationship between a set of covariates and the time until an event of interest occurs, often referred to as the "time-to-event" or "survival time." This method is particularly useful when dealing with censored data, where the event has not occurred for some individuals by the end of the study period, or when the exact time of the event is unknown.
Building a Survival Tree
Constructing a...
Building a Survival Tree
Constructing a...
79
Size-Exclusion Chromatography
549
In size-exclusion chromatography (SEC), also known as molecular-exclusion or gel-permeation chromatography, molecules are separated based on their sizes. This technique is important for separating large molecules such as polymers and biomolecules. The two classes of micron-sized stationary phases encountered in SEC are silica particles and cross-linked polymer resin beads. Both materials are porous, but their pore sizes vary significantly.
Silica particles offer advantages such as rigidity,...
Silica particles offer advantages such as rigidity,...
549
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
48
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
48
Predicting Molecular Geometry
34.3K
VSEPR Theory for Determination of Electron Pair Geometries
34.3K
VSEPR Theory
9.4K
Valence shell electron-pair repulsion theory (VSEPR theory) enables us to predict the molecular structure around a central atom from an examination of the number of bonds and lone electron pairs in its Lewis structure. The VSEPR model assumes that electron pairs in the valence shell of a central atom will adopt an arrangement that minimizes repulsions between these electron pairs by maximizing the distance between them. The electrons in the valence shell of a central atom form either bonding...
9.4K


