图的最小双解集问题研究

Locating source of a rumor in a network is crucial for controlling and preventing diffusion. In this project, we will study source location by modeling it as the minimum doubly resolving set problem. Minimum doubly resolving set problem is a strengthening of the well-studied metric dimension problem, which is introduced independently by Harary and Malter and by Slater in the 1970s. In this project, we mainly study the minimum doubly resolving set problem on hypercube, cographs and unit disk graphs.

在网络中，确定“谣言”的源点对控制和阻止谣言的散播是至关重要的。本项目主要研究在最小双解集问题的模型下来定位谣言的源点。最小双解集问题是已经深入研究的度量维数问题的强化。度量维数是分别由Harary、Malter和Slater于70年代介绍的。本项目主要研究超立方体图、余图及单位圆盘图的最小双解集问题。

本项目研究了稠密图的超欧拉宽度和部分集合多重覆盖问题。我们得到如下结果：对不相邻的顶点对，最大度满足一定条件时，那么超欧拉宽度大于等于s+1或者是在一类图里（完全刻画）；对部分集合多重覆盖问题给出了一个原始对偶算法并且给出近似比。