Finding a maximum matching in a permutation graph

DOI10.1007/BF01178659MaRDI QIDQ1902306zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

maximum matchingpermutation graph

Mathematics Subject Classification ID

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

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

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

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 Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
• Efficient maximum matching algorithms for 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)