论文标题：An exact algorithm with a new upper bound and reductions for maximum edge weighted clique in massive sparse graphs

期刊：Frontiers of Computer Science

作者：Shuli HU, Jiaqi LI, WEN WEN, Yupeng ZHOU, Ruizhi LI, Minghao YIN 

发表时间：9 Jul 2025

DOI：10.1007/s11704-024-40814-y

微信链接：点击此处阅读微信文章

引用格式：

Shuli HU, Jiaqi LI, WEN WEN, Yupeng ZHOU, Ruizhi LI, Minghao YIN. An exact algorithm with a new upper bound and reductions for maximum edge weighted clique in massive sparse graphs. Front. Comput. Sci., 2026, 20(6): 2006402

阅读原文：

问题概述

离散事件系统的网络攻击可诊断性(CA-可诊断性)，用于评估在攻击者干扰传感器与诊断系统通信时对系统的诊断能力。目前判断CA-可诊断性的方法具有较高的时空复杂度。本文介绍了一种新型循环模型(CM)，该模型能够在不构建诊断器的情况下，提高判断离散事件系统CA -可诊断性的效率。

技术步骤

首先，该文提出了一种创新算法——循环检测(DC)算法，用于获取构建CM所需的循环信息。随后，我们拓展了关键观测值在可诊断性检查中的概念，并提出了获取关键观测值(GCO)算法。最后，在提出基于循环模型的CA -可诊断性检查(CMDIC)算法时，我们阐述了CM框架内CA -可诊断性的充分必要条件，并对其算法复杂度进行了分析。

实验结果

下表分别展示了该文的方法以及传统方法在三种静态攻击下判断CA – 可诊断性效率的实验结果。

期刊简介

Frontiers of Computer Science （FCS）是由教育部主管、高等教育出版社和北京航空航天大学共同主办，南京大学支持，SpringerNature 公司海外发行的英文学术期刊。本刊于 2007 年创刊，月刊，全球发行。主要刊登计算机科学领域具有创新性的综述论文、研究论文等。本刊主编为周志华院士，共同主编为熊璋教授。编委会及青年 AE 团队由国内外知名学者及优秀青年学者组成。本刊被 SCI、Ei、DBLP、INSPEC、SCOPUS 和中国科学引文数据库（CSCD）核心库等收录，为 CCF 推荐B类期刊；两次入选“中国科技期刊国际影响力提升计划”；入选“第4届中国国际化精品科技期刊”；两次入选“中国科技期刊卓越行动计划”（一期梯队、二期领军）。

中国学术前沿期刊网

http://journal.hep.com.cn