Convexity, distance invariants and longest paths in graphs

点击翻译按钮获取中文摘要

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.