-
曹皖林: 形式化技术及其应用
Speaker: 曹皖林（美国德州农工大学） Time: 10:20-11:20 (Time in Beijing) November 17, 2023 (Friday) Venue: 518, Research Building 4 Abstract: 软硬件系统开发包括不断地进行优化和验证，形式化方法在这个过程中被广泛应用。本讲座结合芯片开发过程中的最常见逻辑表达方式和分析手段，介绍形式化技术。具体包括以下内容：– 设计的网表表达– BDD 及其应用– 逻辑的计算与近似– 实例：低功耗优化– 讨论：布尔代数、NP问题、抽象及计算 Speaker Bio: 曹皖林，美国Texas A&M 大学博士，合见工业软件集团 fellow。研究兴趣包括：形式化方法，EDA与FPGA工具开发。
-
Claire Hanen: Fixed Parameter Tractability of scheduling dependent typed tasks with time windows
Speaker: Claire Hanen (Sorbonne Université – LIP6) Time: 14:00 (UTC) November 15, 2023 (Wednesday) Venue: Online, Zoom Meeting： Meeting ID: 981 3280 2131 Passcode: 130657 Abstract: This talk discusses the parameterized complexity of scheduling problems, assuming precedence constraints, time windows and typed tasks resource constraints. We recall the usual parameters used for scheduling problems and […]
-
Zile Jiang: Computing Better Approximate Pure Nash Equilibria in Cut Games via Semidefinite Programming
Speaker: Zhile jiang (Aarhus University) Time: 16:20-17:20 (Time in Beijing) November 10, 2023 (Friday) Venue: 518, Research Building 4 Abstract: Cut games are among the most fundamental strategic games in algorithmic game theory. It is well-known that computing an exact pure Nash equilibrium in these games is PLS-hard, so research has focused on computing approximate […]
-
Ton Kloks: Excluding a long double path minor
Speaker: Ton Kloks (National Tsing Hua University ) Time: 10:20-11:20 (Time in Beijing) November 10, 2023 (Friday) Venue: 518, Research Building 4 Abstract: This is a paper from 1994. (In my opinion this paper is a work of art.) The paper proves Robertson’s conjecture on well-quasi-orders by topological minors for classes of graphs that are closed […]
-
Ton Kloks: Excluding a long double path minor
Speaker: Ton Kloks (National Tsing Hua University ) Time: 10:20-11:20 (Time in Beijing) November 3, 2023 (Friday) Venue: 518, Research Building 4 Abstract: This is a paper from 1994. (In my opinion this paper is a work of art.) The paper proves Robertson’s conjecture on well-quasi-orders by topological minors for classes of graphs that are closed […]
-
Huairui Chu: FPT Approximation Using Treewidth
Speaker: Huairui Chu (Nanjing University ) Time: 16:00-17:00 (Time in Beijing) October 25, 2023 (Wednesday) Venue: 518, Research Building 4 Abstract: Treewidth is a useful tool in designing graph algorithms. Although many NP-hard graph problems can be solved in linear time when the input graphs have small treewidth, there are problems which remain hard on […]
-
Zihui Liang: Connectivity in the presence of an opponent
Speaker: Zihui Liang (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) October 20, 2023 (Friday) Venue: 518, Research Building 4 Abstract: The paper introduces two player connectivity games played on finite bipartite graphs. Algorithms that solve these connectivity games can be used as subroutines for solving M\”uller games. M\”uller games […]
-
Kangyi Tian: Parameterized Algorithms for Cluster Vertex Deletion on Degree-4 Graphs and General Graphs
Speaker: Kangyi Tian (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) October 13, 2023 (Friday) Venue: 518, Research Building 4 Abstract: In the Cluster Vertex Deletion problem, we are given a graph G and an integer k, and the goal is to determine whether we can delete at most k […]
-
Haidong Yang: Topological network-control games
Speaker: Haidong Yang (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) September 22, 2023 (Friday) Venue: 518, Research Building 4 Abstract: The paper introduces new combinatorial games, called topological network-control games, played on graphs. These games model the influence of competing two parties aiming to control a given network. In […]
-
Pengpeng Wang: 基于树割映射的网络健壮性增强算法
Speaker: Pengpeng Wang（Henan University of Technology) Time: 16:20-17:20 (Time in Beijing) September 15, 2023 (Friday) Venue: 518, Research Building 4 Abstract: 在大型稀疏网络中，少数几条边的随机故障可能导致网络断开，为了提高网络健壮性，可以选择性的保护特定边从而使整个网络的连通性保持到一定水平，然而资源总是有限的，不可能保护所有的边。我们设计了一种快速的算法，即通过深度遍历树快速定位到较小的割，并对这些割的边进行有选择性的保护，从而提高网络健壮性，传统算法利用线性规划，时间较慢，并且不能适用于大型网络，实验表明我们的算法能够抵御 99.99%的随机故障，有较好的加速效果。 Speaker Bio: 汪鹏鹏现就读于河南工业大学信息科学与工程学院，研究方向为最小割，网络健壮性，稀疏割算法等。