构建和采样分位, 3-均的超图与给定的度数序列
András Hubai1, Tamás Róbert Mezei1, Ferenc Béres2
1HUN-REN Rényi Institute, Budapest, Hungary.
PloS one
|May 15, 2024
概括
确定具有特定度的分位,三均超图的存在是NP-完整的. 然而,对于几乎正规度序列,存在多项式算法,并且一种新的采样方法显示出对超图分析和统计测试的希望.
科学领域:
- 组合学和图形理论
- 计算复杂性 计算复杂性
- 统计建模 统计建模
背景情况:
- 分立的, 3-均的超图是由它们的顶点类和超边缘的特定约束定义的.
- 度数序列问题调查了具有给定度数序列的超图的存在.
- 从具有规定的属性的超图中均取样是一个具有挑战性的计算任务.
研究的目的:
- 为了分析分位,三均的超图的度数序列问题的计算复杂性.
- 开发一个高效的算法,用于一个特定类别的度序列.
- 为了引入一个新型的抽样方法,部分,3-均的超图,并探索其在统计测试中的应用.
主要方法:
- 证明一般度序决策问题的NP完全性.
- 开发一个多项式时间算法,用于几乎正规度序列.
- 实施并行温方法,以取样超图基于度序偏差.
- 将该方法应用于对应急表的奇平方 (χ2) 测试.
主要成果:
- 对于部分的决定问题, 3-均的超图存在是NP-完整的.
- 一个多项式时间算法为几乎正规度序列提供.
- 并行温方法有效地采样超图,并且在 χ2 测试中表现出比标准方法更高的灵敏度,特别是对于小型数据集.
结论:
- 这项研究确立了超图理论中一个基本问题的计算硬度.
- 为特定情况下提供有效的解决方案,增强实际适用性.
- 拟议的抽样技术为超图分析和统计推理提供了一个强大的新工具,在某些场景中性能优于传统方法.
相关概念视频
01:16Stratified Sampling Method
12.0K
Sampling is a technique to select a portion (or subset) of the larger population and study that portion (the sample) to gain information about the population. The sampling method ensures that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest.
To choose a stratified sample, divide the population into groups called strata and then take a...
To choose a stratified sample, divide the population into groups called strata and then take a...
12.0K
01:15Sampling Theorem
329
In signal processing, the analysis of continuous-time signals, denoted as x(t), often involves sampling techniques to convert these signals into discrete-time signals. This process is essential for digital representation and manipulation. A critical component in sampling is the train of impulses, characterized by the sampling interval and the sampling frequency. The relationship between these parameters and the original signal's properties dictates the success of the sampling process.
329
01:16Second Uniqueness Theorem
1.0K
Consider a region consisting of several individual conductors with a definite charge density in the region between these conductors. The second uniqueness theorem states that if the total charge on each conductor and the charge density in the in-between region are known, then the electric field can be uniquely determined.
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the...
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the...
1.0K
01:02Degrees of Freedom
3.0K
The degree of freedom for a particular statistical calculation is the number of values that are free to vary. As a result, the minimum number of independent numbers can specify a particular statistic. The degrees of freedom differ greatly depending on known and uncalculated statistical components.
For example, suppose there are three unknown numbers whose mean is 10; although we can freely assign values to the first and second numbers, the value of the last number can not be arbitrarily...
For example, suppose there are three unknown numbers whose mean is 10; although we can freely assign values to the first and second numbers, the value of the last number can not be arbitrarily...
3.0K
01:20Cluster Sampling Method
11.9K
Appropriate sampling methods ensure that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest.
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
To choose a cluster sample, divide the population into clusters (groups) and then randomly select some of the clusters. All the members from these clusters are in the cluster sample. For example, if you randomly sample four departments from your...
11.9K
01:09Random Sampling Method
11.0K
Sampling is a technique to select a portion (or subset) of the larger population and study that portion (the sample) to gain information about the population. Data are the result of sampling from a population. The sampling method ensures that samples are drawn without bias and accurately represent the population. Because measuring the entire population in a study is not practical, researchers use samples to represent the population of interest. Among the various sampling methods used by...
11.0K