Finding a Maximum Matching in a Circular-Arc Graph

Y. Daniel Liang; Chongkye Rhee

doi:10.1016/0020-0190(93)90117-R

Finding a Maximum Matching in a Circular-Arc Graph

Y. Daniel Liang
, Chongkye Rhee

Computer Science

Indiana Purdue Univ at Fort Wayne
Eastern Kentucky University

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

15 Scopus citations

Abstract

We present an O(n log n) algorithm for finding a maximum matching in a circular-arc graph. The best known algorithm for the same problem in general graphs takes O(√|V| |E|) time.

Original language	American English
Journal	Information Processing Letters
Volume	45
DOIs	https://doi.org/10.1016/0020-0190(93)90117-R
State	Published - Mar 22 1993

Disciplines

Computer Sciences

Access to Document

10.1016/0020-0190(93)90117-RLicense: Unspecified

Cite this

@article{453c5f35024542e8bd92d89c6f2b63b8,

title = "Finding a Maximum Matching in a Circular-Arc Graph",

abstract = " We present an O(n log n) algorithm for finding a maximum matching in a circular-arc graph. The best known algorithm for the same problem in general graphs takes O(√|V| |E|) time. ",

author = "Liang, \{Y. Daniel\} and Chongkye Rhee",

note = "We present an O(n log n) algorithm for finding a maximum matching in a circular-arc graph. The best known algorithm for the same problem in general gr...",

year = "1993",

month = mar,

day = "22",

doi = "10.1016/0020-0190(93)90117-R",

language = "American English",

volume = "45",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Finding a Maximum Matching in a Circular-Arc Graph

AU - Liang, Y. Daniel

AU - Rhee, Chongkye

N1 - We present an O(n log n) algorithm for finding a maximum matching in a circular-arc graph. The best known algorithm for the same problem in general gr...

PY - 1993/3/22

Y1 - 1993/3/22

N2 - We present an O(n log n) algorithm for finding a maximum matching in a circular-arc graph. The best known algorithm for the same problem in general graphs takes O(√|V| |E|) time.

AB - We present an O(n log n) algorithm for finding a maximum matching in a circular-arc graph. The best known algorithm for the same problem in general graphs takes O(√|V| |E|) time.

UR - https://www.sciencedirect.com/science/article/pii/002001909390117R?via%3Dihub

U2 - 10.1016/0020-0190(93)90117-R

DO - 10.1016/0020-0190(93)90117-R

M3 - Article

SN - 0020-0190

VL - 45

JO - Information Processing Letters

JF - Information Processing Letters

ER -

Finding a Maximum Matching in a Circular-Arc Graph

Abstract

Disciplines

Access to Document

Other files and links

Fingerprint

Cite this