An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs

DOI10.1016/S0020-0190(97)00081-1zbMath1336.05131OpenAlexW2062510888MaRDI QIDQ287094

Jean-Luc Fouquet, Henri Thuillier, I. I. Parfenov

Publication date: 26 May 2016

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00081-1

zbMATH Keywords

matchingmodular decomposition

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (5)

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 ⋮ Unnamed Item ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Maximum matching in almost linear time on graphs of bounded clique-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An O(\(n\)) time algorithm for maximum matching on cographs
• On a unique tree representation for \(P_ 4\)-extendible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• An optimal parallel matching algorithm for cographs
• TWO THEOREMS IN GRAPH THEORY
• A New Class of Brittle Graphs
• A Combinatorial Decomposition Theory

This page was built for publication: An \(O(n)\) time algorithm for maximum matching in \(P_{4}\)-tidy graphs