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.