TUHH Open Research
Help
  • Log In
    New user? Click here to register.Have you forgotten your password?
  • English
  • Deutsch
  • Communities & Collections
  • Publications
  • Research Data
  • People
  • Institutions
  • Projects
  • Statistics
  1. Home
  2. CRIS
  3. Funding
  4. Resilient Broadcasting via Independent Spanning-Trees
 
  • Project Details
  • Publications
Options
Akronym
Broadcasting Spannbäume
Projekt Titel
Resilient Broadcasting via Independent Spanning-Trees
Förderkennzeichen
SCHM 3186/2-1
Funding code
945.03-911
Startdatum
October 1, 2020
Enddatum
September 30, 2022
Gepris ID
401348462
Loading...
Thumbnail Image
Funder
Deutsche Forschungsgemeinschaft (DFG)  
Institut
Algorithmen und Komplexität E-11  
Projektleitung
Schmidt, Jens M.  orcid-logo
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.
TUHH
Weiterführende Links
  • Contact
  • Send Feedback
  • Cookie settings
  • Privacy policy
  • Impress
DSpace Software

Built with DSpace-CRIS software - Extension maintained and optimized by 4Science
Design by effective webwork GmbH

  • Deutsche NationalbibliothekDeutsche Nationalbibliothek
  • ORCiD Member OrganizationORCiD Member Organization
  • DataCiteDataCite
  • Re3DataRe3Data
  • OpenDOAROpenDOAR
  • OpenAireOpenAire
  • BASE Bielefeld Academic Search EngineBASE Bielefeld Academic Search Engine
Feedback