【摘 要】
：
该文综述了任意图支配集精确算法分析和设计的新进展.支配集问题是经典NP完全问题,很多问题都能与它相联系.我们针对最小支配集、最大独立集、最小独立支配集、最小连通支配
【机 构】
：
陕西师范大学计算机科学学院,电子科技大学计算机科学与工程学院
论文部分内容阅读
该文综述了任意图支配集精确算法分析和设计的新进展.支配集问题是经典NP完全问题,很多问题都能与它相联系.我们针对最小支配集、最大独立集、最小独立支配集、最小连通支配集、最小加权支配集问题提供了详尽算法描述和实例说明,以使文章自包含方便阅读.文中还讨论了诸如分支简化策略、复杂度分析、测度分析、记忆等技术.自Claude Berge首次准确阐述现代图支配概念后,经过很长一段时期的沉寂,关于指数时间精确算法设计的研究热情在过去五年中显著增涨.除回顾这些最新成果之外,作者还盼望国内研究团体能更加重视这个快速发展的
其他文献
视频事件探测是视频内容自动理解领域的一个重要研究问题.在视频事件探测中,感兴趣对象的运动轨迹常被作为视频中探测事件的一种重要依据.目前基于轨迹的事件探测方法主要集中于根据轨迹几何特征进行视频事件探测,而忽略了与轨迹相关的语义信息.然而我们知道,轨迹的产生往往受到一些与轨迹相关联的语义信息的影响,如轨迹产生时的地理信息等.将轨迹相关联的语义信息整合到轨迹中可以使我们了解更多关于轨迹的信息.语义轨迹为
机关事务标准化是一项全新的课题,在"高质量发展"的主题下,深化简政放权、放管结合、优化服务改革,标准化理念和方法已经融入政府治理之中。如何界定机关事务标准化边界、探
首先简单介绍了计算机内机器数的有关概念,然后着重阐述了机器数的三种表示,最后分析了计算机语言并讨论了它的应用。
下一代互联网高度可扩展支持服务动态部署．越来越多延时和抖动敏感服务（如IPTV、VoIP等）的应用对BGP路由计算的性能提出了更高的需求．路由器采用分布式控制平面和实现并行BGP路由
SaaS模式已成为当前流行的软件服务形式.为满足不同租户个性化的业务服务需求,SaaS模式必须提供灵活的定制机制.为此,提出了一个支持租户业务流程定制行为建模及验证的框架.
传统的用假设验证法进行三维物体识别的方法需要通过一组非线性方程组求解从模型到场景的坐标系变换,具有非常高的复杂度.文中提出了一种基于能够表明物体几何构造的直线段特征的人造物体识别方法,将假设验证法中对于全局坐标系变换的求解分散在各个平面单应性变换的求解中,降低了求解的复杂度.该方法首先利用几何不变量预匹配特征点,进而假设并求出场景和模型平面之间的单应矩阵,随后通过模型与场景之间直线段特征匹配的结果
近年来,基于位置的服务获得了越来越广泛的关注,其中最近邻查询是最常用的一种查询方式.测量手段的不准确性以及数据本身的性质导致不确定性在位置数据中普遍存在,这种不确定性会对最近邻查询结果产生影响.空间中障碍物的存在也给空间数据查询带来了挑战.文中研究存在障碍物的空间中不确定对象连续最近邻查询的处理方法,设计了一种剪枝策略大幅降低需要计算的不确定对象数目,并进一步提出了障碍空间中不确定对象最近邻查询安
密钥管理是无线传感器网络安全机制和服务的基石，随机密钥预分发是当前最有效的密钥管理机制，但目前的随机密钥预分发方案存在一个潜在的挑战：无法同时获取理想的网络安全连通性
虹吸是Petri网的一种重要结构,可以用来分析所模拟系统的许多重要特性,如可达性、可逆性和活性等.文中首先提出了虹吸子网的概念,并给出了将Petri网划分成虹吸子网的多项式算
电气自动化是一门非常重要的学科,学生在实际学习过程中,需要很强的实践能力和应用能力,才能有效提高专业水平和操作水准。针对电气自动化这一专业进行一体化教学策略,可以增