对于大型稀疏图形的顶点加权色彩中代的小组减少
Yi Fan1, Zaijun Zhang1,2, Quan Yu1
1School of Mathematics and Statistic, Qiannan Normal University for Nationalities, Duyun 558000, China.
Entropy (Basel, Switzerland)
|October 28, 2023
概括
这项研究引入了一个新的算法,用于最小顶点加权着色 (MinVWC) 问题,显著减少复杂问题的图形大小. 该方法使用最大集群计数来实现高效的图形缩小.
科学领域:
- 图形理论 图形理论
- 组合优化的优化.
- 计算机科学 计算机科学
背景情况:
- 最小顶点彩色 (MinVC) 问题,一个基本的NP-hard问题,试图将相邻顶点的颜色最小化.
- 最小顶点加权彩色 (MinVWC) 问题通过赋予顶点重量并将使用的颜色的总重量最小化来概括MinVC.
研究的目的:
- 开发一个有效的减少算法,以解决NP-hard的最小垂直加权着色 (MinVWC) 问题.
- 通过创建较小的子图来改进现有的方法,以有效解决问题.
主要方法:
- 提出了一种基于最大集团列举的新型减少算法.
- 该算法采用群组采样和图形缩减,包括有希望的群组缩减,更好的限制缩减和后缩减.
- 它利用来自最大集团比例的下限来指导减少过程.
主要成果:
- 实验结果表明,与大型基准图的最新RedLS方法相比,拟的算法生成的子图要小得多.
- 评估了算法组件的个别影响和实际属性.
- 一个理论结果表明,算法的减少效应相当于给定足够的运行时间的详尽的最大集群列举.
结论:
- 开发的基于最大集群计数的减少算法对MinVWC问题非常有效.
- 它在子图减小方面提供了显著的改进,优于最近的方法.
- 该算法提供了一种理论上合理且实际上高效的方法来解决复杂的图形着色问题.
相关概念视频
Vector Algebra: Graphical Method
12.2K
Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
12.2K
Block Diagram Reduction
221
The process of deriving the transfer function of a control system often involves reducing its block diagram to a single block. This simplification can be achieved through a series of strategic operations, including relocating branch points and comparators. These operations preserve the overall function of the system while allowing for easier manipulation and combination of blocks.
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
The first step in this process is the identification and relocation of a branch point. A branch point, where a...
221
Reducing Line Loss
156
In a three-phase circuit, line loss is an indicator of energy dissipated as heat due to the resistance of transmission lines. To address this, incorporating transformers into the system—a step-up transformer at the source and a step-down transformer at the load—is a strategic solution. Two three-phase transformers are introduced to improve this.
With a step-up transformer at the source, the voltage is increased, thereby reducing the current in the transmission lines since power loss...
With a step-up transformer at the source, the voltage is increased, thereby reducing the current in the transmission lines since power loss...
156
Woodward–Hoffmann Selection Rules and Microscopic Reversibility
3.1K
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
3.1K
Routh-Hurwitz Criterion II
260
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
260
Routh-Hurwitz Criterion I
254
Consider an electrical power grid, where stability is essential to prevent blackouts. The Routh-Hurwitz criterion is a valuable tool for assessing system stability under varying load conditions or faults. By analyzing the closed-loop transfer function, the Routh-Hurwitz criterion helps determine whether the system remains stable.
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
To apply the Routh-Hurwitz criterion, a Routh table is constructed. The table's rows are labeled with powers of the complex frequency variable s, starting from the...
254


