-
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: 汪鹏鹏现就读于河南工业大学信息科学与工程学院，研究方向为最小割，网络健壮性，稀疏割算法等。
-
Yan Gu:Recent Advances in Parallel Algorithm Design
Speaker: Yan Gu（University of California, Riverside) Time: 16:20-17:20 (Time in Beijing) September 8, 2023 (Friday) Venue: 518, Research Building 4 Abstract: This talk will cover some new advances in recent parallel algorithm research. We will introduce a few new parallel algorithms on classic graph problems such as single-source shortest paths (the rho-stepping and the delta*-stepping […]
-
Yan Gu:Introduction to Parallel Algorithms
Speaker: Yan Gu（University of California, Riverside) Time: 10:20-11:20 (Time in Beijing) September 8, 2023 (Friday) Venue: 518, Research Building 4 Abstract: Parallel processors are ubiquitous nowadays and it is almost impossible to find a single-core processor, probably other than a toaster. However, very few courses and online materials cover the basic knowledge for designing parallel […]
-
Yiding Feng: Mobility Data in Operations: The Facility Location Problem
Speaker: Yiding Feng（University of Chicago) Time: 11:00-12:00 (Time in Beijing) August 4, 2023 (Friday) Venue: 518, Research Building 4 Abstract: Speaker Bio: Yiding Feng is a postdoctoral principal researcher at the University of Chicago Booth School of Business. Previously, he worked as a postdoctoral researcher at Microsoft Research New England from 2021 to 2023. He […]
-
Louxin Zhang: A Scalable Algorithm for Inferring Phylogenetic Networks from Trees
Speaker: Louxin Zhang （新加坡国立大学） Time: July 3, 2023 (Monday) 10:30-11:30am Venue: 电子科技大学清水河校区主楼B1-501 Abstract: Phylogenetic networks are rooted, acyclic directed graph in which leaves are labelled with genes, genomes or species. They are used to model evolution with reticulate events. The reconstruction of phylogenetic networks is an important but challenging problem in phylogenetics and genome evolution, […]
-
Chao Xu: Matroid Base with Congruency Constraint
Speaker: Chao Xu (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) June 9, 2023 (Friday) Venue: 518, Research Building 4 Abstract: Let $k$ be an integer and $M$ a matroid on groundset $E$.There is a label function $\ell:E\to [k]$ that assigns a label to all elements. We aim to identify […]
-
Yuhang Guo: Characterization of Monotonic Allocation in Multi-unit Diffusion Auction
Speaker: Yuhang Guo (University of Electronic Science and Technology of China) Time: 16:20-17:20 (Time in Beijing) June 2, 2023 (Friday) Venue: 518, Research Building 4 Abstract: Designing strategyproof mechanisms in multi-unit diffusion auctions has posed a significant challenge, as each agent’s allocation and price can be easily influenced by their invitees and siblings. In our […]