报告题目：Optimized Degree Realizations

报告人：David Peleg，魏茨曼科学研究所

报告时间：2025年11月5日（周三）9:00

报告地点：23-506

报告摘要：The degree realization problem requires, given a sequence $d$ of $n$ positive integers, to decide whether there exists a graph whose degrees correspond to $d$, and to construct such a graph if it exists. A more challenging variant of the problem arises when $d$ has many different realizations, and some of them may be more desirable than others. We consider optimized degree realization problems in which the goal is to compute a realization that optimizes some quality measure. In particular, we discuss efficient algorithms for the problems of finding a realization with the maximum clique, the maximum independent set, the minimum dominating set, the maximum matching, and more.

报告人简介：David Peleg于1980年获得以色列理工学院（Technion）学士学位，1985年获得以色列魏茨曼科学研究所（Weizmann Institute）计算机科学博士学位。此后，他在IBM阿尔马登研究中心（IBM Almaden）和斯坦福大学（Stanford University）从事博士后研究工作。1988年，他加入魏茨曼科学研究所计算机科学与应用数学系，目前担任该所“诺曼・D・科恩计算机科学讲席教授”（Norman D. Cohen Professorial Chair of Computer Sciences）。他的研究方向包括分布式网络算法、容错计算、通信网络理论、近似算法与图论；他不仅著有《分布式计算：一种局部敏感方法》（Distributed Computing: A Locality-Sensitive Approach）一书，还在这些领域发表了多篇学术论文。

邀请人：冉颖丽