A linear time algorithm for the maximum matching problem on cographs

DOI10.1007/BF01990526zbMath0818.68090MaRDI QIDQ1314631

Ming-Shing Yu, Cheng-Hsing Yang

Publication date: 7 March 1994

Published in: BIT (Search for Journal in Brave)

zbMATH Keywords

data structurescographsmaximum matching problem

Mathematics Subject Classification ID

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

Cites Work

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

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