BACK to VOLUME 28 NO.1

Kybernetika 28(1):37-49, 1992.

Minimum Cut in Directed Planar Networks

Ladislav Janiga and Václav Koubek


Abstract:

An algorithm which for any planar directed network with n nodes finds its minimum cut in time $O(n log^2(n)/ log (log (n)))$ is presented. For the case of s-t -network this time is reduced by the factor of $log (n)$, i. e. to $O(n log (n)/log (log (n)))$.


download full-text.pdf
download abstract.pdf

BIB TeX

@article{kyb:1992:1:37-49,

author = {Janiga, Ladislav and Koubek, V\'{a}clav},

title = {Minimum Cut in Directed Planar Networks},

journal = {Kybernetika},

volume = {28},

year = {1992},

number = {1},

pages = {37-49}

publisher = {{\'U}TIA, AV {\v C}R, Prague },

}


BACK to VOLUME 28 NO.1