A linear time algorithm for the maximum matching problem on cographs

DOI10.1007/BF01990526MaRDI QIDQ1314631zbMATH OpenFDO

Authors Ming-Shing Yu, C. H. Yang

Publication date 7 March 1994

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01990526

zbMATH Keywords

cographsdata structuresmaximum matching problem

Mathematics Subject Classification ID

Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Cites work

• A simple parallel tree contraction algorithm
• 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

(2)

• A linear time algorithm for maximum matchings in convex, bipartite graphs
• scientific article; zbMATH DE number 279491 (Why is no real title available?)

This page was built for publication: A linear time algorithm for the maximum matching problem on cographs

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