Finding a maximum matching in a permutation graph
type: Item
instance of: scholarly article
title: Finding a maximum matching in a permutation graph
zbMATH Open document ID: 0831.68076
DOI: 10.1007/BF01178659
author: Y. Daniel Liang
author: Chongkye Rhee
published in: Acta Informatica
publication date: 1995-11-20T00:00:00Z
review text: We present an \({\mathcal O} (n \log \log n)\) time algorithm for finding a maximum matching in a permutation graph with \(n\) vertices, assuming that the input graph is represented by a permutation.
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 818364
zbMATH Keywords: maximum matching
zbMATH Keywords: permutation graph
MaRDI profile type: Publication
cites work: TWO THEOREMS IN GRAPH THEORY
cites work: Paths, Trees, and Flowers
cites work: Preserving order in a forest in less than logarithmic time and linear space
cites work: An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
cites work: Finding a maximum matching in a circular-arc graph
cites work: Transitive Orientation of Graphs and Identification of Permutation Graphs
cites work: On Comparability and Permutation Graphs
cites work: An O(\(n\)) time algorithm for maximum matching on cographs
full work available at URL: https://doi.org/10.1007/bf01178659
OpenAlex ID: W1969693641
Recommended article: Finding a maximum independent set in a permutation graph
Recommended article: Maximum matchings in regular graphs
Recommended article: Finding all the perfect matchings in bipartite graphs
Recommended article: The maximum number of perfect matchings in graphs with a given degree sequence
Recommended article: Efficient algorithms for finding maximum matching in graphs
Recommended article: Finding a maximum matching in a circular-arc graph
Recommended article: Maximum induced matchings in graphs
Recommended article: Maximum matching in regular and almost regular graphs
Recommended article: Finding all maximally-matchable edges in a bipartite graph
Recommended article: Maximum matchings in general graphs through randomization
description: scientific article; zbMATH DE number 818364