-
Quasi-Isometric Graph-Simplifications
Speaker: Roger Su(University of Auckland) Time: 10:00-12:00 (Time in Beijing) 15:00-17:00 (Time in Auckland) October 29, 2021 (Friday) Venue: Qingshuihe Campus Abstract: Quasi-isometries are a concept originally used to study infinite algebraic objects. Here we apply quasi-isometries to finite graphs, and propose a theoretical framework for simplifying large-scale graphs. This framework consists of several goals, […]
-
Subset Feedback Vertex Set in Chordal Graph
Speaker: Tian Bai(University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) October 15, 2021 (Friday) Venue: Qingshuihe Campus Abstract: The Subset Feedback Vertex Set (SFVS) problem takes as input a graph and a subset of vertices in . The task is to find a minimal set of […]
-
Approximation Algorithms for TTP-3
Speaker: Jingyang Zhao(University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) September 10, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/dm/xKZlIrcZhk0Z ID: 704 420 285 Venue: Qingshuihe Campus Abstract: The Traveling Tournament Problem is a complex combinatorial optimization problem in tournament timetabling, which asks us to design a double round-robin […]
-
Heuristic Algorithms for Steiner Tree Problem
Speaker: Xinyu Wu (University of Electronic and Science Technology of China) Time: 10:00-11:00 (Time in Beijing) 14:00-15:00 (Time in Auckland) September 3, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/dm/WlulUnrGJ0NM?rs=25 ID: 969 615 091 Venue: Qingshuihe Campus Abstract: The Steiner tree problem (STP) is a challenging NP-hard problem that commonly arises in practical applications as one of many […]
-
Improving Maximum k-Plex Solver via Second-Order Reduction and Graph Color Bounding
Speaker: Shan Hu (University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) June 25, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/s/Epf69wfHFBWm ID: 171 763 214 Venue: Main Building Abstract: In a graph, a k-plex is a vertex set in which every vertex is not adjacent to at most k […]
-
PPSZ on unique-kSAT
Speaker: Jian Ma (University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) June 11, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/s/jSsMAf9XBBZ7 ID: 166 684 100 Venue: Main Building Abstract: The CNF satisfiability problem is defined as follows: given a CNF formula , decide if there exists truth-value assignment to […]
-
A Fast Algorithm for SAT in Terms of Formula Length
Speaker: Junqiang Peng (University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) June 4, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/s/2p05iZpS1RvT ID: 973 577 922 Password: 1949 Venue: Main Building Abstract: The CNF satisfiability problem is defined as follows: given a CNF formula , decide if there exists a […]
-
Random Sampling of Important Separators: New Bounds and New Applications
Speaker: Huairui Chu (University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) May 28, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/s/xtCxnutcKyYJ ID: 447 185 012 Password: 1949 Venue: Main Building Abstract: Important separator is a well-known concept for solving problems about graphs in parameterized algorithm sense. Marx and Razgon […]
-
Kernelization for Feedback Vertex Set based on linear programming
Speaker: Tian Bai (University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) May 21, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/s/QfT7QuGrXPBQ ID: 582 848 199 Password: 1949 Venue: Main Building Abstract: Feedback Vertex Set (FVS) is a problem to determine whether a given undirected graph has a vertex set […]
-
Kernels for Planar Vertex-Disjoint Triangle Packing
Speaker: Zimo Sheng (University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) May 14, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/s/oLdo3h9nEQlW ID: 655 461 488 Venue: Main Building Abstract: Triangle Packing is an important class of NP-hard problem. In this paper, we study Parameterized Planar Vertex-Disjoint Triangle Packing problem, […]