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 | |
State | Published - Mar 22 1993 |
Disciplines
- Computer Sciences
Keywords
- Interval graphs
- algorithms
- circular-arc graphs
- graph theory
- maximum matching