Convexity, distance invariants and longest paths in graphs

网络是交通、通信和计算机网络的有用模型。在这个提议中，我们感兴趣的问题是通过某个最优子网连接网络中的S个节点集。这可以是(i)包含S的最短连接子网，即。，节点数最少或（ii）包含S的连通子网是最小的，即如果任何不在S中的节点从子网中删除，则断开S。S相对于这两种连接S的最优方式中的任何一种的间隔由属于连接S的最短子网（或包含S的最小子网）的所有节点组成。一个节点集T是凸的或闭的，如果它包含T的每个子集S具有固定大小的区间。我们提出研究这些闭集具有某些性质的网络结构。

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.