Algorithm design techniques based on transformation into network structure

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

Our aim is to design algorithms for discrete optimization problems with graph structure. We have obtained approximation algorithms and exact algorithms for several NP-hard but important problems such as the maximum independent set problem.We have theoretically analyzed the approximation ratios of our approximation algorithms and derived upper bounds on the time complexities of our exact algorithms.In particular, for designing exact algorithms, we have devised new design techniques such as amortization by shifts, decomposition by cut-pairs,and how to compute the largest root of a set of recursive equations.