Place: NIDTEC
Date and Time: December 7, 2016, 10am.
Speaker: Tadashi Akagi
Title: Optimal Edge Fault-Tolerant Embedding of a Star over a Cycle
Abstract:
An embedding of a guest graph G over a host graph H, such that the vertices of G are included in the vertices of H, consists of a mapping ρ that associates every edge e = xy in G to an x−y-path ρ(e) in H. Given an edge f in H, the number of edges e in G such that f belongs to ρ(e) is called the (edge) congestion of f. The length of ρ(e) is called the dilatation of e. The sum of all the dilatations is the cost of the embedding. The removal of an edge f of H gives rise to a surviving graph Gf , consisting of the guest graph without those edges that cross f , i.e., Gf = G − {e : f ∈ ρ(e)}.
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.