An O(n) time algorithm for maximum matching on cographs
From MaRDI portal
Publication:685476
DOI10.1016/0020-0190(93)90230-7zbMATH Open0776.68063OpenAlexW1966596093MaRDI QIDQ685476FDOQ685476
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)
Cites Work
- Title not available (Why is that?)
- Clustering and domination in perfect graphs
- Complement reducible graphs
- Title not available (Why is that?)
- Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
- A Linear Recognition Algorithm for Cographs
- A simple parallel tree contraction algorithm
- An Amortized Analysis of Insertions into AVL-Trees
Cited In (15)
- The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes
- The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
- An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Linear-time algorithm for the matched-domination problem in cographs
- A linear-time algorithm for maximum-cardinality matching on cocomparability graphs
- Title not available (Why is that?)
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
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)
