论文标题
对冲连通性而没有对冲重叠
Hedge Connectivity without Hedge Overlaps
论文作者
论文摘要
连接性是图理论的中心概念，在图算法设计和应用中起着重要作用。随着网络中新兴的新应用程序，新型的图形连接问题已经引起了人们的注意 - 赫奇连接性。在本文中，我们考虑了没有树篱重叠的对冲图的模型，其中边缘被分配到称为套期保值的子集中，称为围困。图形的对冲连接性是将拆卸断开图形连接的对冲数量。该模型比超图更一般，这带来了新的计算挑战。是否可以在多项式时间内解决这个问题，这是一个漫长的开放问题。在本文中，我们根据其最大条件以及对冲收缩操作研究对冲图连接的组合性能，而无需对冲重叠，这些条件为其算法进步提供了新的见解。
Connectivity is a central notion of graph theory and plays an important role in graph algorithm design and applications. With emerging new applications in networks, a new type of graph connectivity problem has been getting more attention--hedge connectivity. In this paper, we consider the model of hedge graphs without hedge overlaps, where edges are partitioned into subsets called hedges that fail together. The hedge connectivity of a graph is the minimum number of hedges whose removal disconnects the graph. This model is more general than the hypergraph, which brings new computational challenges. It has been a long open problem whether this problem is solvable in polynomial time. In this paper, we study the combinatorial properties of hedge graph connectivity without hedge overlaps, based on its extremal conditions as well as hedge contraction operations, which provide new insights into its algorithmic progress.
