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)

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.

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
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• TWO THEOREMS IN GRAPH THEORY

Cited in

(8)

• On two-processor scheduling and maximum matching in permutation graphs
• Planar stage graphs: Characterizations and applications
• An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs
• OPTIMAL PARALLEL MATCHING ON BIPARTITE PERMUTATION 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
• Finding maximum matchings in RDV graphs efficiently

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)