We study the problem of deisgning fault-tolerant routings for a communication network which is a triconnected planar network of processors in the surviving route graph model. The surviving route graph for a graph G, a routing rho and a set of faults F is a directed graph consisting of nonfaulty nodes with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing rho . In this paper, we show that we can construct a routing for any triconnected planar graph with a triangle face such that the diameter of the surviving route graphs is two(thus optimal) for any faults F(|F|<=2). We also show that the optimal routing can be computed in linear time.
展开▼
机译：我们研究了在生存的路由图模型中为通信网络设计容错路由的问题，该网络是处理器的三连接平面网络。图G，路由rho和一组故障F的生存路由图是有向图，它由具有从节点x到节点y的有向边的非故障节点组成，前提是从x到y的路由中没有故障。生存路线图的直径可能是图G和路线rho的容错措施之一。在本文中，我们证明了我们可以为具有三角形面的任何三连通平面图构造一个路由，使得对于任何故障F（| F | <= 2），存活的路由图的直径都是2（因此是最优的）。我们还表明，可以在线性时间内计算出最佳路由。
展开▼
