论文标题
算法的算法上限
Algorithmic upper bounds for graph geodetic number
论文作者
论文摘要
基于最短路径的理论问题是研究的核心，因为它们的理论重要性和适用性。本文处理的是，这是简单连接图的全局度量，它属于涵盖问题的路径：什么是最小信号的顶点集，因此其元素之间的所有最短路径涵盖了图的每个顶点。受近期文献中精确的0-1整数线性编程形式主义的启发，我们提出了一种新方法，以算法的方式获得大地测量数的上限。这些算法的效率在结构上不同的图表集合中得到了证明。
Graph theoretical problems based on shortest paths are at the core of research due to their theoretical importance and applicability. This paper deals with the geodetic number which is a global measure for simple connected graphs and it belongs to the path covering problems: what is the minimal-cardinality set of vertices, such that all shortest paths between its elements cover every vertex of the graph. Inspired by the exact 0-1 integer linear programming formalism from the recent literature, we propose a new methods to obtain upper bounds for the geodetic number in an algorithmic way. The efficiency of these algorithms are demonstrated on a collection of structurally different graphs.
