良构图类上的模型检测问题

作     者：刘国航 陈翌佳 LIU Guo-Hang;CHEN Yi-Jia

作者机构：上海交通大学电子信息与电气工程学院上海200240 

基　　金：国家自然科学基金面上项目(62372291) 

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2025年第36卷第3期

页      码：1107-1130页

摘      要：图上的诸多计算问题都是NP难问题,因此经常会将问题限定在一些特定的图类上.这类方法在过去的几十年间收获了大量特定图类(如度有界图类、树宽有界图类、平面图类等)上的高效算法,其中很大一部分都能统一到算法元定理的框架下.算法元定理是一类通用的结论,主要描述模型检测问题(即判定结构的逻辑性质)的高效算法.现有的算法元定理主要基于现代结构图论,并且大多研究固定参数易解算法,即参数复杂性意义下的高效算法.在许多良构的图类上,一些常见逻辑(如一阶逻辑和一元二阶逻辑)的模型检测问题是固定参数易解的.由于不同逻辑的表达能力不同,不同图类上的模型检测问题的易解性也有显著的区别,因此探索易解的最大范围也是算法元定理研究的重要课题.研究表明,一阶逻辑模型检测问题的易解性与图的稀疏性密切关联.经过数十年的努力,目前学界对于稀疏图类的认识已经较为成熟,近年的研究重心逐渐转向一些良构的稠密图类,研究也面临着更多的挑战.目前在稠密图类上已经得到了若干深刻的算法元定理,相关的探索仍在继续.将全局性地介绍算法元定理领域的发展,旨在为国内的相关研究提供一些线索和助力.

主 题 词：模型检测 算法元定理 稀疏性 结构图论 参数复杂性 

学科分类：08[工学] 0835[0835] 081202[081202] 0812[工学-测绘类] 

核心收录：

D　O　I：10.13328/j.cnki.jos.007201

馆 藏 号：203157654...