Finding a maximum matching in a permutation graph
From MaRDI portal
Publication:1902306
DOI10.1007/BF01178659zbMATH Open0831.68076OpenAlexW1969693641MaRDI QIDQ1902306FDOQ1902306
Authors: 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
Recommendations
- Finding a maximum independent set in a permutation graph
- Maximum matchings in regular graphs
- Finding all the perfect matchings in bipartite graphs
- The maximum number of perfect matchings in graphs with a given degree sequence
- Efficient algorithms for finding maximum matching in graphs
- Finding a maximum matching in a circular-arc graph
- Maximum induced matchings in graphs
- Maximum matching in regular and almost regular graphs
- Finding all maximally-matchable edges in a bipartite graph
- Maximum matchings in general graphs through randomization
Cites Work
- Paths, Trees, and Flowers
- Preserving order in a forest in less than logarithmic time and linear space
- Transitive Orientation of Graphs and Identification of Permutation Graphs
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- TWO THEOREMS IN GRAPH THEORY
- An O(\(n\)) time algorithm for maximum matching on cographs
- On Comparability and Permutation Graphs
- Finding a maximum matching in a circular-arc graph
Cited In (4)
- An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs
- A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
- Efficient maximum matching algorithms for trapezoid graphs
- Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
This page was built for publication: Finding a maximum matching in a permutation graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1902306)
