An improved algorithm for the planar 3-cut problem

Xin He

doi:10.1016/0196-6774(91)90021-P

An improved algorithm for the planar 3-cut problem

Xin He

Department of Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

15 Scopus citations

Abstract

A 3-cut of a connected graph G is a subset of edges which, when deleted, separates G into three connected components. In this paper we present an O(n log n) algorithm for finding a minimum 3-cut in planar graphs. Our algorithm improves the best previously known algorithm for the problem by an O( n log n) factor.

Original language	English
Pages (from-to)	23-37
Number of pages	15
Journal	Journal of Algorithms
Volume	12
Issue number	1
DOIs	https://doi.org/10.1016/0196-6774(91)90021-P
State	Published - Mar 1991

Access to Document

10.1016/0196-6774(91)90021-P

Cite this

@article{83550bd9196c4d0c8ebb8fdd330aa53c,

title = "An improved algorithm for the planar 3-cut problem",

abstract = "A 3-cut of a connected graph G is a subset of edges which, when deleted, separates G into three connected components. In this paper we present an O(n log n) algorithm for finding a minimum 3-cut in planar graphs. Our algorithm improves the best previously known algorithm for the problem by an O( n log n) factor.",

author = "Xin He",

year = "1991",

month = mar,

doi = "10.1016/0196-6774(91)90021-P",

language = "English",

volume = "12",

pages = "23--37",

journal = "Journal of Algorithms",

issn = "0196-6774",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - An improved algorithm for the planar 3-cut problem

AU - He, Xin

PY - 1991/3

Y1 - 1991/3

N2 - A 3-cut of a connected graph G is a subset of edges which, when deleted, separates G into three connected components. In this paper we present an O(n log n) algorithm for finding a minimum 3-cut in planar graphs. Our algorithm improves the best previously known algorithm for the problem by an O( n log n) factor.

AB - A 3-cut of a connected graph G is a subset of edges which, when deleted, separates G into three connected components. In this paper we present an O(n log n) algorithm for finding a minimum 3-cut in planar graphs. Our algorithm improves the best previously known algorithm for the problem by an O( n log n) factor.

UR - https://www.scopus.com/pages/publications/0003165538

U2 - 10.1016/0196-6774(91)90021-P

DO - 10.1016/0196-6774(91)90021-P

M3 - Article

AN - SCOPUS:0003165538

SN - 0196-6774

VL - 12

SP - 23

EP - 37

JO - Journal of Algorithms

JF - Journal of Algorithms

IS - 1

ER -

An improved algorithm for the planar 3-cut problem

Abstract

Access to Document

Other files and links

Fingerprint

Cite this