Finding a maximum matching in a permutation graph

Chongkye Rhee, Y. Daniel Liang

Research output: Contribution to journalArticlepeer-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 languageAmerican English
JournalActa Informatica
Volume45
DOIs
StatePublished - Mar 22 1993

Disciplines

  • Computer Sciences

Keywords

  • Interval graphs
  • algorithms
  • circular-arc graphs
  • graph theory
  • maximum matching

Fingerprint

Dive into the research topics of 'Finding a maximum matching in a permutation graph'. Together they form a unique fingerprint.

Cite this