An O(\(n\)) time algorithm for maximum matching on cographs

DOI10.1016/0020-0190(93)90230-7zbMath0776.68063OpenAlexW1966596093MaRDI QIDQ685476

Ming-Shing Yu, Cheng-Hsing Yang

Publication date: 17 October 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90230-7

zbMATH Keywords

maximum matchingcographs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Related Items (13)

An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs ⋮ Finding a maximum matching in a permutation graph ⋮ A Linear-Time Algorithm for Maximum-Cardinality Matching on Cocomparability Graphs ⋮ The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes ⋮ Unnamed Item ⋮ The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Role colouring graphs in hereditary classes ⋮ On some graphs with a unique perfect matching ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Linear-time algorithm for the matched-domination problem in cographs ⋮ Maximum matching in almost linear time on graphs of bounded clique-width

Cites Work

• Unnamed Item
• Unnamed Item
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Clustering and domination in perfect graphs
• Complement reducible graphs
• A Linear Recognition Algorithm for Cographs
• An Amortized Analysis of Insertions into AVL-Trees
• A simple parallel tree contraction algorithm

This page was built for publication: An O(\(n\)) time algorithm for maximum matching on cographs