An O(n) time algorithm for maximum matching in P₄-tidy graphs

DOI10.1016/S0020-0190(97)00081-1MaRDI QIDQ287094zbMATH OpenOpenAlexFDO

Authors Jean-Luc Fouquet, I. Parfenoff, Henri Thuillier

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

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

Recommendations

• An efficient parallel algorithm for maximum matching for some classes of graphs
• Finding a maximum matching in a permutation graph
• scientific article; zbMATH DE number 1496857
• Recognition algorithm for P₄-tidy graphs
• scientific article; zbMATH DE number 1375569

Cites work

• A Combinatorial Decomposition Theory
• A New Class of Brittle Graphs
• A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
• A tree representation for \(P_ 4\)-sparse graphs
• An O(n) time algorithm for maximum matching on cographs
• An optimal parallel matching algorithm for cographs
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• scientific article; zbMATH DE number 3708283 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• On a unique tree representation for \(P_ 4\)-extendible graphs
• TWO THEOREMS IN GRAPH THEORY

Cited in

(8)

• An efficient parallel algorithm for maximum matching for some classes of graphs
• 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
• scientific article; zbMATH DE number 1375569 (Why is no real title available?)
• Recognition algorithm for P₄-tidy graphs
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• On adaptive algorithms for maximum matching

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

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