Advanced Multilevel Node Separator Algorithms

摘要: A node separator of a graph is subset S the nodes such that removing and its incident edges divides into two disconnected components about equal size. In this work, we introduce novel algorithms to find small separators in large graphs. With focus on solution quality, flow-based local search which are integrated multilevel framework. addition, transfer techniques successfully used partitioning field. This includes usage edge ratings tailored our problem guide coarsening algorithm as well highly localized iterated cycles improve quality even further. Experiments indicate own framework already competitive terms quality. Adding additional further improves Our strongest configuration almost always outperforms competing systems while average computing 10i¾ź% 62i¾ź% smaller than Metis Scotch, respectively.