Parameterized Algorithms in Graph Analysis

PhD Qualifying Examination


Title: "Parameterized Algorithms in Graph Analysis"

by

Mr. Pingjiang LI

Abstract:

Parameterization is a technique that can make the original problem instances 
have more restrictions. With this additional restriction, we can somehow lower 
the difficulty of the original problem, and thus design more efficient 
algorithms to solve the problem. Especially, we can make a lot of NP-hard 
problems have kind of polynomial time algorithms after the parameterization.

In this survey, I will describe one graph sparsity parameter, treewidth and 
explain how we can make use of this parameter to have faster algorithms.


Date:                   Monday, 22 April 2024

Time:                   2:00pm - 4:00pm

Venue:                  Room 4475
                        Lifts 25/26

Committee Members:      Dr. Amir Goharshady (Supervisor)
                        Dr. Jiasi Shen (Chairperson)
                        Prof. Cunsheng Ding
                        Prof. Pedro Sander