Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - A fast algorithm for minimum weight odd cuts and circuits in planar graphs
AU - Letchford, A N
AU - Pearson, N
PY - 2005
Y1 - 2005
N2 - We give a simple O(n^{3/2} log n) algorithm for finding a minimum weight odd circuit in planar graphs. By geometric duality, the same algorithm can be used to find minimum weight odd cuts. For general sparse graphs, the fastest known algorithms for these two problems take O(n^2 log n) time and O(n^3 log n) time, respectively.
AB - We give a simple O(n^{3/2} log n) algorithm for finding a minimum weight odd circuit in planar graphs. By geometric duality, the same algorithm can be used to find minimum weight odd cuts. For general sparse graphs, the fastest known algorithms for these two problems take O(n^2 log n) time and O(n^3 log n) time, respectively.
KW - Planar graphs
KW - Combinatorial optimisation
U2 - 10.1016/j.orl.2004.12.001
DO - 10.1016/j.orl.2004.12.001
M3 - Journal article
VL - 33
SP - 625
EP - 628
JO - Operations Research Letters
JF - Operations Research Letters
SN - 0167-6377
IS - 6
ER -