CAJ | 학술논문

s-图的路由数源自于网格上行走的机器人的坐标规则问题.Onn和Sperner指出该问题是NP-完全的并进而提出这样一个问题:平面图上的路由数是否一定存在仅由半径为参数构成的界?本文引入有向s-图的路由数这一概念并证明该数等于其周长.这一结果表明无向s-图的路由数等于该图所有定向图的最小周长,同时也对上面的问题给出了一个反例.做为一个应用,我们证明乘积图的路由数等于其半径.
s-도적로유수원자우망격상행주적궤기인적좌표규칙문제.Onn화Sperner지출해문제시NP-완전적병진이제출저양일개문제:평면도상적로유수시부일정존재부유반경위삼수구성적계?본문인입유향s-도적로유수저일개념병증명해수등우기주장.저일결과표명무향s-도적로유수등우해도소유정향도적최소주장,동시야대상면적문제급출료일개반례.주위일개응용,아문증명승적도적로유수등우기반경.
The routing number of an s-graph arises in the social-law approach to the problem of coordination of robots moving on a network. Onn and Sperber showed that the determination of the routing number of an sgraph is NP-complete and further posed the question of whether planar graphs always admit routing numbers that can be bounded in terms of their radius. In this paper, we introduce the routing number of the directed sgraph and show that it is equal to the perimeter (i. e. the length of a longest directed cycle) of the directed sgraph. This implies that the routing number of an undirected s-graph is equal to the minimum perimeter among all its orientations. Using this result ,we give a counter example to a question of Onn et al. and further show that the routing number of the product graph, a graph frequently used as a network, is equal to its radius and hence can be determined in polynomial time.