{"id":189,"date":"2016-11-26T11:10:49","date_gmt":"2016-11-26T15:10:49","guid":{"rendered":"http:\/\/192.168.1.5\/?p=189"},"modified":"2018-07-30T16:01:25","modified_gmt":"2018-07-30T20:01:25","slug":"theory-seminar-optimal-edge-fault-tolerant-embedding-of-a-star-over-a-cycle","status":"publish","type":"post","link":"https:\/\/nidtec.pol.una.py\/index.php\/2016\/11\/26\/theory-seminar-optimal-edge-fault-tolerant-embedding-of-a-star-over-a-cycle\/","title":{"rendered":"Theory Seminar: Optimal Edge Fault-Tolerant Embedding of a Star over a Cycle"},"content":{"rendered":"<p><strong>Place:<\/strong> <a href=\"http:\/www.cc.pol.una.py\/events\/theory-seminar\/\">NIDTEC<\/a><\/p>\n<p><strong>Date and Time:<\/strong> December 7, 2016, 10am.<\/p>\n<p><strong>Speaker:<\/strong>\u00a0Tadashi Akagi<\/p>\n<p><strong>Title:<\/strong>\u00a0Optimal Edge Fault-Tolerant Embedding of a\u00a0Star over a Cycle<\/p>\n<p><strong>Abstract:\u00a0<\/strong><\/p>\n<p>An\u00a0embedding\u00a0of a guest graph\u00a0G\u00a0over a host graph\u00a0H, such that the\u00a0vertices of\u00a0G\u00a0are included in the vertices of\u00a0H, consists of a\u00a0mapping\u00a0\u03c1\u00a0that\u00a0associates every edge\u00a0e\u00a0=\u00a0xy\u00a0in\u00a0G\u00a0to an\u00a0x\u2212y-path\u00a0\u03c1(e) in\u00a0H. Given an edge\u00a0f\u00a0in\u00a0H, the number of edges\u00a0e\u00a0in\u00a0G\u00a0such that\u00a0f\u00a0belongs to\u00a0\u03c1(e) is called the\u00a0(edge) congestion of\u00a0f. The length of\u00a0\u03c1(e) is called the\u00a0dilatation\u00a0of\u00a0e. The\u00a0sum of all the dilatations is the\u00a0cost\u00a0of the\u00a0embedding. The removal of an\u00a0edge\u00a0f\u00a0of\u00a0H\u00a0gives rise to a\u00a0surviving graph\u00a0Gf\u00a0, consisting of the guest graph\u00a0without those edges that cross\u00a0f\u00a0, i.e.,\u00a0Gf\u00a0=\u00a0G\u00a0\u2212 {e\u00a0:\u00a0f\u00a0\u2208\u00a0\u03c1(e)}.<\/p>\n<p>Given positive integers\u00a0n,\u00a0b, and an\u00a0n\u00a0nodes graph\u00a0H\u00a0with a distinguished\u00a0vertex\u00a0v, we are facing the problem of finding a graph\u00a0G\u00a0\u2282\u00a0Kn\u00a0with minimum\u00a0cost embedding over\u00a0H, in such a way that for each surviving graph\u00a0Gf,\u00a0there exists another upper embedding of the\u00a0complete graph\u00a0K1,n\u00a0over\u00a0Gf\u00a0that keeps the congestion of every\u00a0e\u00a0in\u00a0Gf\u00a0below\u00a0b, while pairs the vertex of\u00a0degree\u00a0n\u00a0with\u00a0v.<\/p>\n<p>The problem has direct applications to the design of resilient Internet-\u00a0Service-Providers backbones; specifically to connect customer\u00a0aggregation\u00a0points towards data-centers or other prominent nodes. This work presents a\u00a0general lower bound for the optimal cost of such\u00a0a problem, and also intro-\u00a0duces a family of graphs whose minimal embeddings match that bound for\u00a0all values of\u00a0n\u00a0and\u00a0b, when the host\u00a0graph is the cycle\u00a0Cn, thus determining\u00a0a family of optimal solutions for these instances.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Place: NIDTEC Date and Time: December 7, 2016, 10am. Speaker:\u00a0Tadashi Akagi Title:\u00a0Optimal Edge Fault-Tolerant Embedding of a\u00a0Star over a Cycle Abstract:\u00a0 An\u00a0embedding\u00a0of a guest graph\u00a0G\u00a0over a host graph\u00a0H, such that the\u00a0vertices of\u00a0G\u00a0are included in the vertices of\u00a0H, consists of a\u00a0mapping\u00a0\u03c1\u00a0that\u00a0associates <a href=\"https:\/\/nidtec.pol.una.py\/index.php\/2016\/11\/26\/theory-seminar-optimal-edge-fault-tolerant-embedding-of-a-star-over-a-cycle\/\" class=\"read-more\">Leer m\u00e1s&#8230;<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-189","post","type-post","status-publish","format-standard","hentry","category-actividades-academicas"],"_links":{"self":[{"href":"https:\/\/nidtec.pol.una.py\/index.php\/wp-json\/wp\/v2\/posts\/189","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nidtec.pol.una.py\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nidtec.pol.una.py\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nidtec.pol.una.py\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nidtec.pol.una.py\/index.php\/wp-json\/wp\/v2\/comments?post=189"}],"version-history":[{"count":1,"href":"https:\/\/nidtec.pol.una.py\/index.php\/wp-json\/wp\/v2\/posts\/189\/revisions"}],"predecessor-version":[{"id":190,"href":"https:\/\/nidtec.pol.una.py\/index.php\/wp-json\/wp\/v2\/posts\/189\/revisions\/190"}],"wp:attachment":[{"href":"https:\/\/nidtec.pol.una.py\/index.php\/wp-json\/wp\/v2\/media?parent=189"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nidtec.pol.una.py\/index.php\/wp-json\/wp\/v2\/categories?post=189"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nidtec.pol.una.py\/index.php\/wp-json\/wp\/v2\/tags?post=189"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}