Convexity, distance invariants and longest paths in graphs

网络是交通、通信和计算机网络的有用模型。在这个方案中，我们感兴趣的是通过某个最优子网连接一个网络中的一组S节点的问题。这可以是(I)包含S的最短连通子网，即具有最小节点数，或(Ii)包含S的连通子网，其在以下意义上是最小的：如果从该子网中删除任何不在S中的节点，则这断开S。S相对于这两种连接S的最佳方式中的任一种的间隔由属于连接S的某个最短子网(或包含S的某个最小子网)的所有节点组成。一个节点集T是凸的或闭的，如果它包含对T的每个具有固定大小的子集S的区间。我们建议研究这些闭集具有一定性质的网络结构。 该提案的第二部分应用于网络空间中的机器人导航。地标是放置在网络中的节点上的设备，它允许机器人确定其到地标的距离。如果网络中的两个位置与地标的距离不同，则通过地标来区分它们。目标是确定最少的地标及其位置，以便网络中的任何两个位置通过一些地标来区分。同样的想法也适用于网络安全。不安装地标，而是安装探测设备，使人们能够唯一地确定入侵者的位置。这是一个很难解决的问题。我们建议开发新的方法，为所需的最小数量的地标/检测设备提供良好的边界，并为来自特定类型网络的网络提供准确的解决方案。 该提案的第三部分涉及定向网络。例如，它们被用来为单行道或循环赛的网络建模。在后一种情况下，团队成为网络的节点，并且如果T1击败T2，则存在从团队T1到团队T2的有向弧。我们建议研究循环赛的扩展结构及其与最长路径的关系。

Networks are useful models for transportation, communication and computer networks. In this proposal we are interested in the problem of connecting a set S of nodes in a network by some optimal subnetwork. This could be (i) a shortest connected subnetwork containing S ,i.e., with the smallest number of nodes or (ii) a connected subnetwork containing S that is minimal in the sense that if any node not in S is deleted from the subnetwork, then this disconnects S. The interval for S with respect to either of these two optimal ways of connecting S consist of all nodes that belong to some shortest subnetwork connecting S (or some minimal subnetwork containing S). A set T of nodes is convex or closed if it contains the interval for every subset S of T having a fixed size. We propose to study structures of networks for which these closed sets have certain properties. The second part of this proposal has applications to the navigation of robots in a network space. A landmark is a device placed at a node in the network that allows a robot to determine its distance to the landmark. Two positions in the network are distinguished by some landmark if they are at different distances from the landmark. The goal is to determine the fewest number of landmarks and their locations so that any two positions in the network are distinguished by some landmark. The same ideas have application to network security. Instead of installing landmarks one installs detecting devices that allow one to uniquely determine the location of an intruder. This is a very difficult problem to solve. We propose to develop new approaches that give good bounds for the smallest number of landmarks/detecting devices that are needed and exact solutions for networks from a specified type of network. The third part of this proposal deals with directed networks. These are used, for example, to model networks with one-way streets or round robin tournaments. In the latter case the teams become the nodes of the network and there is a directed arc from a team T1 to a team T2 if T1 beat T2. We propose to study structures that are extensions of round robin tournaments and their relation to longest paths.