A Hall-type theorem with algorithmic consequences in planar graphs

DOI10.1016/j.disc.2024.113892arXiv2304.05859OpenAlexW4391197469MaRDI QIDQ6197750

Hossein Jowhari, Ebrahim Ghorbani

Publication date: 19 February 2024

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2304.05859

zbMATH Keywords

planar graphsmaximum matchingdata stream algorithms

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Nonnumerical algorithms (68W05) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Unnamed Item
• Unnamed Item
• Lower bounds on the cardinality of the maximum matchings of planar graphs
• Structural results on matching estimation with applications to streaming
• Tight bounds on maximal and maximum matchings
• An estimator for matching size in low arboricity graphs with two applications
• Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
• The binding number of a graph and its Anderson number

This page was built for publication: A Hall-type theorem with algorithmic consequences in planar graphs