Linear Algebraic Techniques in Algorithmic Graph Theory

点击翻译按钮获取中文摘要

Algorithms for fundamental graph problems are important tools in computer science and engineering.  Extensive research has been done in the past decades to develop efficient algorithms, most of them based on combinatorial techniques.  In recent years, new linear algebraic techniques have been developed to make surprising and significant progress in these fundamental problems.  My previous research develops linear algebraic techniques to design both better approximation algorithms and faster exact algorithms for graph problems.  I plan to continue this line of ongoing research and have identified three promising directions to investigate.