无桥图最短偶子图覆盖的上界

偶子图覆盖问题是图论研究领域的的重要内容之一,为研究最小偶子图覆盖猜想,利用整数流与偶子图覆盖的联系,借助于整数4-流在图的某个圈中扩充的结论,给出并证明了无桥图的最小偶子图覆盖的一个新的上界,改进了范更华给出的结论。

二进制翻译中代码生成的子图覆盖算法

二进制翻译技术能够有效解决二进制兼容问题,促进新型体系结构的发展,也是虚拟机技术的重要组成部分,具有重要的研究和应用价值,但是其效率仍然有待提升,特别是目标代码生成的效率。设计了一种高效的目标代码生成算法——代码生成的子图覆盖算法(subgraph covering for code generation,SCCG),能够以尽可能少的代价生成精简的目标代码。该算法应用数据流图对二进制代码中的基本块进行建模,获取指令间的数据相关,并采用基于子图覆盖的贪心算法得到目标代码。在TransARM原型系统中进行了实现和测试,结果表明该算法获得了更优质的目标代码,并且成本得到了有效控制。

整数流与子图覆盖

整数流和子图覆盖是当今图论领域的两个重要研究方向,与著名的四色问题密切相关.四色问题等价于平面图的整数4-流问题.一个图有整数k-流,当且仅当对该图的某个定向,存在从边集合到k阶交换群的一个函数,使得对图中每个点,进入该点的边函数值之和等于离开该点的边函数值之和.整数流理论与数学其他领域一些著名问题有一定的关联,如组合学的孤独跑步者、数论的丢番图逼近、几何学的视线阻碍和线性空间堆垒基等.四色问题还等价于平面图的偶子图覆盖问题:是否存在3个偶子图,覆盖一个2-边连通平面图的每条边恰好两次.著名的Fulkerson猜想认为,对每个2-边连通图(不必是平面图),存在6个偶子图,覆盖该图的每条边恰好4次.本文对整数流和子图覆盖这两个研究方向及相关问题的历史和现状作一个综述.