Research on algorithms based on graph minor theory

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

Although algorithms based on the graph minor theory run in polynomial time, they are theoretically and practically far from efficient algorithms. In this research, we gave a faster algorithm for the disjoint paths problem with a fixed number of terminal pairs, which improves the running time from O(n^3) to O(n^2),where n is the number of the input graph. Furthermore, we gave a simpler and faster algorithm for some problems if the input graph is in restricted classes.