Resilient Broadcasting via Independent Spanning-Trees

通过独立生成树进行弹性广播

• 批准号: 401348462
• 负责人: Professor Dr. Jens M. Schmidt
• 金额: --
• 依托单位: Lehrstuhl für Algorithmen und Komplexität
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2018
• 资助国家: 德国
• 起止时间: 2017-12-31 至 2023-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/401348462?language=en
• 关键词: Resilient; Broadcasting; via; Independent; Spanning

A classic theoretical measure for the resilience of a communication network is its edge-connectivity. However, for some network problems, this measure is not known to be suitable at all. In resilient broadcasting, for example, one prescribed vertex r communicates with every other vertex through a set of spanning trees such that, for every vertex v, the paths from r to v in these spanning trees are edge-disjoint (such trees are called independent). But it is unknown how exactly the maximal number of independent spanning trees in a network relate to its edge-connectivity, and nothing more is known for the analogous question regarding vertex-failures or for the complexity of finding such independent spanning trees.In fact, the long-standing Edge-Independent Spanning Tree Conjecture in graph theory states that every k-edge-connected network contains k independent spanning trees. A proof of this conjecture would not only characterize the networks in which resilient broadcasting is possible, but arguably also deliver the structural insights that are necessary for the compact design of such networks and for efficient routing schemes in these. Although there is recent structural and algorithmic progress on this conjecture for small k (in which case the conjecture is true), a generalization to higher k was not achieved so far.This project aims at attacking the Edge-Independent Spanning Tree Conjecture for higher k, using the recently proposed structures. We will use graph-theoretic methods in order to search for the right generalization to higher k but also computer-assisted algorithms to support this search.

通信网络弹性的一个经典理论度量是其边缘连通性。然而，对于某些网络问题，这种措施根本不适合。例如，在弹性广播中，一个指定的顶点r通过一组生成树与每个其他顶点通信，使得对于每个顶点v，这些生成树中从r到v的路径是边不相交的（这样的树被称为独立的）。但是，我们并不知道网络中独立生成树的最大数目与其边连通性之间的关系，也不知道类似的顶点失效问题和寻找独立生成树的复杂性。事实上，图论中的边独立生成树猜想（Edge-Independent Spanning Tree Conjecture）指出，每个k-边连通网络都包含k棵独立生成树。这一猜想的证明将不仅表征网络中的弹性广播是可能的，但可以说也提供了结构的见解，这是必要的紧凑的设计，这样的网络和高效的路由方案在这些。虽然最近的结构和算法的进展，这个猜想小k（在这种情况下，猜想是真的），推广到更高的k还没有实现至今。这个项目的目的是攻击边独立生成树猜想高k，使用最近提出的结构。我们将使用图论的方法，以寻找正确的推广到更高的k，但也计算机辅助算法来支持这种搜索。