Combining Crown Structures for Vulnerability Measures

doi:10.1007/s00453-025-01348-2

Combining Crown Structures for Vulnerability Measures

2025-11-21

0

PRE

AI

Aikaterini Niklanovits

DOI：10.1007/s00453-025-01348-2

原文链接

原文求助

摘要

En 中文

过去几十年来，图论领域出现了多种指标以把握网络脆弱性的复杂特性。本文研究了两种特定度量：(加权)顶点完整性(wVI)和(加权)连通分量阶连通性(wCOC)。这些度量不仅评估需要移除多少顶点才能将图分解为碎片，还考虑了剩余最大连通分量的大小。本文的主要焦点是针对这两种度量的核化算法。我们利用不同冠分解（crown decomposition）所固有的结构属性，通过战略性地结合这些属性，引入了新型核化算法，从而推动了当前领域的研究进展。具体而言，我们扩展了Casel等人[1]提出的平衡冠分解的适用范围，并拓展了冠分解技术的应用范围。总结而言，我们将VI的顶点核从p(3)改进为(3)p(2)，将wVI的顶点核从p(3)改进为3(p(2) + p(1.5)p & ell;)，其中p & ell; < p表示移除解后最重分量（heaviest component）的权重。对于wCOC，我们将顶点核从O(k²W + kW²)改进为3(k + root μ W)，其中μ = max(k, W)。我们还给出了一种组合算法，当以r为参数时（其中r ≤ k是一个最大(W + 1)-packing的大小），可在固定参数可解时间内提供一个2kW的顶点核。此外，我们还证明，计算COC的2kW顶点核的算法可以转化为针对两种特殊情况的多项式算法，即当W = 1时（对应于著名的顶点覆盖问题），以及对于爪形自由图（claw-free graphs）。具体而言，我们展示了一种仅通过使用冠结构（crown structures）即可获得2k顶点核（或获得2-近似）的顶点覆盖问题的新方法。

Keyword:

Crown decomposition

Kernelization

Vertex Integrity

Component order connectivity

Combining Crown Structures for Vulnerability Measures

摘要

期刊

机构

引用论文