Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00177 Algorithm Engineering for Optimal Graph Bipartization Falk Hüffner Vol. 13, no. 2, pp. 77-98, 2009. Regular paper Abstract 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.
|
Submitted: November 2007. Published: February 2009. Final: September 2008. Accepted: August 2008. Communicated by Dorothea Wagner |
| Journal of Graph Algorithms and Applications |