Convexity, distance invariants and longest paths in graphs

图中的凸性、距离不变量和最长路径

• 批准号: 198281-2011
• 负责人: Oellermann, Ortrud
• 金额: $ 0.73万
• 依托单位: University of Winnipeg
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=546210
• 关键词: Convexity; distance; invariants; longest; paths

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.

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