Journal of Graph Algorithms and Applications Algorithm Engineering for Optimal Graph Bipartization

Journal of Graph Algorithms and Applications Algorithm Engineering for Optimal Graph Bipartization
复制标题

DOI：
--
复制
发表时间：
--
期刊：
--
影响因子：
--
通讯作者：
Falk Hüffner
Falk Hüffner
中科院分区：
其他
文献类型：
--
作者：
Falk Hüffner

文献摘要

被引文献

相似文献

We examine exact algorithms for the NP-hard Graph Bipartization problem. The task is, given a graph, to find a minimum set of vertices to delete to make it bipartite. Based on the " iterative compression " method introduced by Reed, Smith, and Vetta in 2004, we present new algorithms and experimental results. The worst-case time complexity is improved. Based on new structural insights, we give a simplified correctness proof. This also allows us to establish a heuristic improvement that in particular speeds up the search on dense graphs. Our best algorithm can solve all instances from a testbed from computational biology within minutes, whereas established methods are only able to solve about half of the instances within reasonable time.