An O ( VE ) algorithm for ear decompositions of matching-covered graphs

DOI10.1145/1103963.1103969MaRDI QIDQ2944500zbMATH OpenOpenAlexFDO

Authors Marcelo H. de Carvalho, Joseph Cheriyan

Publication date 2 September 2015

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1103963.1103969

zbMATH Keywords

ear decompositionsmatching theory

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• An O(VE) algorithm for ear decompositions of matching-covered graphs
• Ear decompositions of matching covered graphs
• scientific article; zbMATH DE number 4101262
• Optimal ear decompositions of matching covered graphs and bases for the matching lattice
• scientific article; zbMATH DE number 1342146
• Ear decompositions of join covered graphs
• scientific article; zbMATH DE number 7150552
• Ear decomposition of factor-critical graphs and number of maximum matchings
• Ear-slicing for matchings in hypergraphs
• The two ear theorem on matching-covered graphs

Cited in

(11)

• Optimal ear decompositions of matching covered graphs and bases for the matching lattice
• Ear decomposition and induced even cycles
• Disclosing barriers: a generalization of the canonical partition based on Lovász's formulation
• An O(VE) algorithm for ear decompositions of matching-covered graphs
• Even cycles and perfect matchings in claw-free plane graphs
• scientific article; zbMATH DE number 3958744 (Why is no real title available?)
• scientific article; zbMATH DE number 4101262 (Why is no real title available?)
• scientific article; zbMATH DE number 7150552 (Why is no real title available?)
• Algorithms for (0, 1,d)-graphs withdconstrains
• Computing the forcing spectrum of outerplanar graphs in polynomial time
• Edge-coloured graphs with only monochromatic perfect matchings and their connection to quantum physics

This page was built for publication: An O ( VE ) algorithm for ear decompositions of matching-covered graphs

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