An Elimination Game - Old and New

Professor Esmond Ng

Department Head and Senior Scientist,
Applied Mathematics Department,
Computational Research Division,
Lawrence Berkeley National Laboratory

SIAM Fellow


Date: 11 December 2017 (Monday)
Time: 10:30-11:30 a.m. (Preceded by Reception at 10:00a.m.)

FSC1217 Fong Shu Chuen Building, Ho Sin Hang Campus,
Hong Kong Baptist University



We consider a game on an undirected graph, in which vertices are eliminated. When a vertex is eliminated, the incident edges are removed, but new edges may be added to the graph according to a prescribed rule. The edges that are added will eventually be removed at later stages of the game. The graph will be empty at end of the game. We are interested in the total number of new edges that the game sees throughout the elimination. The order in which the vertices are eliminated will affect the number of new edges added to the graph. Thus, we are interested in finding an elimination order that minimizes a function, which depends on the number of new edges added during the game. In this talk, we will provide an overview of the elimination game. We will also discuss some old and new results on the complexity of the game. This elimination game is relevant to the problem of computing a triangular factorization of a sparse matrix.



All are welcome