The connectivity of a graph is an important parameter to measure its reliability. Structure and substructure connectivity, component connectivity and $k$-restricted connectivity are well-known generalizations of the concept of connectivity, which have been extensively studied from the combinatorial point of view. Very little result is known about their complexity other than the recently obtained computational complexity of $k$-restricted edge-connectivity. In this paper, we zero in on characterizing the complexity of structure and substructure connectivity, component connectivity and $k$-restricted connectivity of graphs, showing that they are all NP-complete.
翻译：图表的连通性是测量其可靠性的一个重要参数。结构和次结构连通性、部件连通性和限制的美元连通性是众所周知的连通概念的概括,从组合角度对连通性概念进行了广泛研究,除了最近获得的以美元限制的边缘连通性计算复杂性以外,其复杂性方面鲜为人知。本文对结构和次结构连通性的复杂性、部件连通性和限制的美元连通性作了说明,显示图的连通性都已完成。
相关内容
微信扫码咨询专知VIP会员