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

DOI10.1016/0020-0190(93)90230-7MaRDI QIDQ685476zbMATH OpenOpenAlexFDO

Authors Ming-Shing Yu, C. H. 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

cographsmaximum matching

Mathematics Subject Classification ID

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

Cites work

• A Linear Recognition Algorithm for Cographs
• A simple parallel tree contraction algorithm
• An Amortized Analysis of Insertions into AVL-Trees
• Clustering and domination in perfect graphs
• Complement reducible graphs
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• scientific article; zbMATH DE number 3896983 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)

Cited in

(15)

• On some graphs with a unique perfect matching
• Finding a maximum matching in a permutation graph
• Role colouring graphs in hereditary classes
• Maximum matching in almost linear time on graphs of bounded clique-width
• The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
• The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
• An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs
• Linear-time algorithm for the matched-domination problem in cographs
• scientific article; zbMATH DE number 1003276 (Why is no real title available?)
• scientific article; zbMATH DE number 1471731 (Why is no real title available?)
• A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• The use of a pruned modular decomposition for maximum matching algorithms on some graph classes
• On adaptive algorithms for maximum matching
• scientific article; zbMATH DE number 279491 (Why is no real title available?)

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q685476)