一个准确的算法,以找到一个最大的重量集团在一个加权的非定向图
Kati Rozman1, An Ghysels2, Dušanka Janežič3
1Faculty of Mathematics, Natural Sciences and Information Technologies, University of Primorska, Glagoljaška Ulica 8, 6000, Koper, Slovenia.
Scientific reports
|April 20, 2024
概括
我们开发了MaxCliqueWeight,这是一个更快的算法,用于在加权图中找到最大重量群. 这种新方法显著提高了复杂图形类型的计算速度,有助于药物发现等研究.
科学领域:
- 图形理论 图形理论
- 计算复杂性 计算复杂性
- 生物信息学是一种生物信息学.
背景情况:
- 在各种领域,包括计算生物学和网络分析中,最大重量集团问题至关重要.
- 现有的算法在大而密集的图形上难以实现计算效率.
研究的目的:
- 介绍MaxCliqueWeight,这是一个用于最大重量集团问题的新算法.
- 提高计算速度和效率,用于在加权图中识别群体.
- 为研究界提供一个免费可用的工具.
主要方法:
- 开发了一种高效的分支和边界方法.
- 集成了一个新的加权图色算法来确定上限的重量.
- 在最多 10,000 个节点的随机和 DIMACS 基准图表上评估性能.
主要成果:
- 与现有的算法相比,MaxCliqueWeight在计算速度方面取得了显著的改进.
- 在高密度随机和DIMACS图表上,其性能优于替代品数量级.
- 该算法的效率在大规模图形分析中尤为显著.
结论:
- MaxCliqueWeight在解决最大重量集团问题方面取得了重大进展.
- 该算法的速度和效率有助于在药物发现等领域的应用.
- MaxCliqueWeight及其变体的开放可用性促进了更广泛的研究采用和创新.
相关概念视频
Vector Algebra: Graphical Method
12.1K
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.1K
Weighted Mean
5.1K
While taking the arithmetic, geometric, or harmonic mean of a sample data set, equal importance is assigned to all the data points. However, all the values may not always be equally important in some data sets. An intrinsic bias might make it more important to give more weightage to specific values over others.
For example, consider the number of goals scored in the matches of a tournament. While computing the average number of goals scored in the tournament, it may be more important to...
For example, consider the number of goals scored in the matches of a tournament. While computing the average number of goals scored in the tournament, it may be more important to...
5.1K
Routh-Hurwitz Criterion II
235
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...
235
Theorems of Pappus and Guldinus: Problem Solving
738
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
738
The Maximum Power Transfer Theorem
605
Consider a linear AC Thevenin equivalent circuit connected to a load impedance.
The load connected draws the current, and the circuit delivers the power to the load. The alternating current flowing through the load is determined using the rectangular form of voltages, currents, network impedance, and load impedance. The average power delivered to the load is obtained from the product of the square of current and load resistance.
The load connected draws the current, and the circuit delivers the power to the load. The alternating current flowing through the load is determined using the rectangular form of voltages, currents, network impedance, and load impedance. The average power delivered to the load is obtained from the product of the square of current and load resistance.
605
Maximum Deflection
474
When analyzing beams under unsymmetrical loads, such as a train moving on a bridge, it is crucial to accurately determine the points of maximum stress and deflection. The process involves identifying the maximum deflection of the beam, which may not always occur at its midpoint due to the uneven distribution of the load.
The maximum deflection occurs at a specific point, known as point O, where the tangent to the deflection curve is horizontal. To find point O, the slope of the tangent at any...
The maximum deflection occurs at a specific point, known as point O, where the tangent to the deflection curve is horizontal. To find point O, the slope of the tangent at any...
474


