Geodesic
Algorithm Engineering for Optimal Graph Bipartization
Journal of graph algorithms and applications, Tome 13 (2009) no. 2, pp. 77-98 Cet article a éte moissonné depuis la source Journal of Graph Algorythms and Applications website

Voir la notice de l'article

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.
DOI : 10.7155/jgaa.00177
Keywords: NP-hard, graph bipartization, fixed-parameter algorithm, iterative compression 
@article{JGAA_2009_13_2_a0,
     author = {Falk H\"uffner},
     title = {Algorithm {Engineering} for {Optimal} {Graph} {Bipartization}},
     journal = {Journal of graph algorithms and applications},
     pages = {77--98},
     year = {2009},
     volume = {13},
     number = {2},
     doi = {10.7155/jgaa.00177},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00177/}
}
TY  - JOUR
AU  - Falk Hüffner
TI  - Algorithm Engineering for Optimal Graph Bipartization
JO  - Journal of graph algorithms and applications
PY  - 2009
SP  - 77
EP  - 98
VL  - 13
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00177/
DO  - 10.7155/jgaa.00177
LA  - en
ID  - JGAA_2009_13_2_a0
ER  - 
%0 Journal Article
%A Falk Hüffner
%T Algorithm Engineering for Optimal Graph Bipartization
%J Journal of graph algorithms and applications
%D 2009
%P 77-98
%V 13
%N 2
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00177/
%R 10.7155/jgaa.00177
%G en
%F JGAA_2009_13_2_a0
Falk Hüffner. Algorithm Engineering for Optimal Graph Bipartization. Journal of graph algorithms and applications, Tome 13 (2009) no. 2, pp. 77-98. doi: 10.7155/jgaa.00177

Cité par Sources :