–
2021-10-26
日時: 2021年10月26日(火) 13:00-15:00
会場: Zoom によるオンライン開催
講演者: Niranka Banerjee (The Institute of Mathematical Sciences)
題目: A Survey on Fault Tolerant Graph Algorithms
概要: Real life networks are prone to failures and are thus unreliable. A failure of a link (or a small number of links) in the network may lead to a breakdown in communication. This motivates us to build networks that are resilient to failures, leading to the field of fault tolerant network design. There are two well known models in the area: fault tolerant subgraphs and fault tolerant oracles. In this talk our aim will be to look at a few well known upper and lower bound results for basic graph problems like shortest paths, matching and cuts in one or both these models. We will conclude with some interesting directions of future work.
本研究会は科研費学術変革領域(A)「社会変革の源泉となる革新的アルゴリズム基盤の創出と体系化」(AFSA)との共催となります．