Home > Research > Publications & Outputs > A fast algorithm for minimum weight odd cuts an...

Research

Links

Text available via DOI:

Keywords

View graph of relations

A fast algorithm for minimum weight odd cuts and circuits in planar graphs

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

A fast algorithm for minimum weight odd cuts and circuits in planar graphs. / Letchford, A N; Pearson, N.
In: Operations Research Letters, Vol. 33, No. 6, 2005, p. 625-628.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Letchford, AN & Pearson, N 2005, 'A fast algorithm for minimum weight odd cuts and circuits in planar graphs', Operations Research Letters, vol. 33, no. 6, pp. 625-628. https://doi.org/10.1016/j.orl.2004.12.001

APA

Letchford, A. N., & Pearson, N. (2005). A fast algorithm for minimum weight odd cuts and circuits in planar graphs. Operations Research Letters, 33(6), 625-628. https://doi.org/10.1016/j.orl.2004.12.001

Vancouver

Letchford AN, Pearson N. A fast algorithm for minimum weight odd cuts and circuits in planar graphs. Operations Research Letters. 2005;33(6):625-628. doi: 10.1016/j.orl.2004.12.001

Author

Letchford, A N ; Pearson, N. / A fast algorithm for minimum weight odd cuts and circuits in planar graphs. In: Operations Research Letters. 2005 ; Vol. 33, No. 6. pp. 625-628.

Bibtex

@article{8d3b5246983d445a82be0f14c6261d5a,
title = "A fast algorithm for minimum weight odd cuts and circuits in planar graphs",
abstract = "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.",
keywords = "Planar graphs, Combinatorial optimisation",
author = "Letchford, {A N} and N Pearson",
year = "2005",
doi = "10.1016/j.orl.2004.12.001",
language = "English",
volume = "33",
pages = "625--628",
journal = "Operations Research Letters",
issn = "0167-6377",
publisher = "Elsevier",
number = "6",

}

RIS

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 -