Finding a maximum matching in a permutation graph

Chongkye Rhee; Y. Daniel Liang

doi:10.1007/BF01178659

Finding a maximum matching in a permutation graph

Chongkye Rhee
, Y. Daniel Liang

Computer Science

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

2 Scopus citations

Abstract

We present anO(n log logn) time algorithm for finding a maximum matching in a permutation graph withn vertices, assuming that the input graph is represented by a permutation.

Original language	American English
Journal	Acta Informatica
Volume	45
DOIs	https://doi.org/10.1007/BF01178659
State	Published - Mar 22 1993

Disciplines

Computer Sciences

Keywords

Interval graphs
algorithms
circular-arc graphs
graph theory
maximum matching

Access to Document

10.1007/BF01178659License: Unspecified

Cite this

@article{fa7c1909e6164c298d010f13f4b2aed0,

title = "Finding a maximum matching in a permutation graph",

abstract = " We present anO(n log logn) time algorithm for finding a maximum matching in a permutation graph withn vertices, assuming that the input graph is represented by a permutation. ",

keywords = "Interval graphs, algorithms, circular-arc graphs, graph theory, maximum matching",

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

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.1007/BF01178659",

language = "American English",

volume = "45",

journal = "Acta Informatica",

issn = "0001-5903",

publisher = "Springer New York",

}

TY - JOUR

T1 - Finding a maximum matching in a permutation graph

AU - Rhee, Chongkye

AU - Liang, Y. Daniel

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 anO(n log logn) time algorithm for finding a maximum matching in a permutation graph withn vertices, assuming that the input graph is represented by a permutation.

AB - We present anO(n log logn) time algorithm for finding a maximum matching in a permutation graph withn vertices, assuming that the input graph is represented by a permutation.

KW - Interval graphs

KW - algorithms

KW - circular-arc graphs

KW - graph theory

KW - maximum matching

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

U2 - 10.1007/BF01178659

DO - 10.1007/BF01178659

M3 - Article

SN - 0001-5903

VL - 45

JO - Acta Informatica

JF - Acta Informatica

ER -

Finding a maximum matching in a permutation graph

Abstract

Disciplines

Keywords

Access to Document

Other files and links

Fingerprint

Cite this