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.