论文标题
在结构稀疏图中的短距离表示
Representation of short distances in structurally sparse graphs
论文作者
论文摘要
图$ g $的部分取向$ \ vec {h} $是一个薄弱的$ r $ - 指导系统，如果对于$ g $中的任何两个顶点，最多的两个顶点$ r $ in $ g $，则在它们之间存在最短的路径$ p $，因此除了$ \ vec {h} $ directs this Edge in this Edge to this Edge to this Edge Edge。如果$ \ vec {h} $具有最大超级限制，则可以有效地表示$ g $中最多$ r $的最短路径。我们表明，来自许多自然图类别的图形都接受了这种弱引导系统，并研究了该概念的算法方面。
A partial orientation $\vec{H}$ of a graph $G$ is a weak $r$-guidance system if for any two vertices at distance at most $r$ in $G$, there exists a shortest path $P$ between them such that $\vec{H}$ directs all but one edge in $P$ towards this edge. In case $\vec{H}$ has bounded maximum outdegree, this gives an efficient representation of shortest paths of length at most $r$ in $G$. We show that graphs from many natural graph classes admit such weak guidance systems, and study the algorithmic aspects of this notion.
