Finding a maximum matching in a permutation graph

DOI10.1007/BF01178659zbMath0831.68076OpenAlexW1969693641MaRDI QIDQ1902306

Y. Daniel Liang, Chongkye Rhee

Publication date: 20 November 1995

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01178659

zbMATH Keywords

maximum matchingpermutation graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (2)

Efficient maximum matching algorithms for trapezoid graphs ⋮ Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs

Cites Work

• An O(\(n\)) time algorithm for maximum matching on cographs
• Finding a maximum matching in a circular-arc graph
• Preserving order in a forest in less than logarithmic time and linear space
• TWO THEOREMS IN GRAPH THEORY
• On Comparability and Permutation Graphs
• Paths, Trees, and Flowers
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Finding a maximum matching in a permutation graph