Date and Time: December 7, 2016, 10am.
Speaker: Tadashi Akagi
Title: Optimal Edge Fault-Tolerant Embedding of a Star over a Cycle
Given positive integers n, b, and an n nodes graph H with a distinguished vertex v, we are facing the problem of finding a graph G ⊂ Kn with minimum cost embedding over H, in such a way that for each surviving graph Gf, there exists another upper embedding of the complete graph K1,n over Gf that keeps the congestion of every e in Gf below b, while pairs the vertex of degree n with v.
The problem has direct applications to the design of resilient Internet- Service-Providers backbones; specifically to connect customer aggregation points towards data-centers or other prominent nodes. This work presents a general lower bound for the optimal cost of such a problem, and also intro- duces a family of graphs whose minimal embeddings match that bound for all values of n and b, when the host graph is the cycle Cn, thus determining a family of optimal solutions for these instances.