FINDING A MAXIMUM MATCHING IN A PERMUTATION GRAPH

Authors
RHEE C LIANG YD
Citation
C. Rhee et Yd. Liang, FINDING A MAXIMUM MATCHING IN A PERMUTATION GRAPH, Acta informatica, 32(8), 1995, pp. 779-792
Citations number
13
Categorie Soggetti
Information Science & Library Science","Computer Science Information Systems
Journal title
Acta informatica → ACNP
ISSN journal
00015903
Volume
32
Issue
8
Year of publication
1995
Pages
779 - 792
Database
ISI
SICI code
0001-5903(1995)32:8<779:FAMMIA>2.0.ZU;2-5
Abstract
We present an O(n log log n) time algorithm for finding a maximum matc hing in a permutation graph with n vertices, assuming that the input g raph is represented by a permutation.