Efficient maximum matching algorithms for trapezoid graphs

DOI10.5614/ejgta.2017.5.1.2zbMath1467.05204OpenAlexW2606560227MaRDI QIDQ5006595

Van-Thieu Vu, Ngoc Khang Le, Phan Thuan Do

Publication date: 16 August 2021

Published in: Electronic Journal of Graph Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.5614/ejgta.2017.5.1.2

zbMATH Keywords

maximum matchingtrapezoid graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Transversal (matching) theory (05D15)

Related Items (2)

An efficient implementation of the Gale and Shapley “propose-and-reject” algorithm ⋮ Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithm for the vertex connectivity of trapezoid graphs
• A polynomial-time algorithm for computing \(K\)-terminal residual reliability of \(d\)-trapezoid graphs
• Trapezoid graphs and generalizations, geometry and algorithms
• Counting the number of vertex covers in a trapezoid graph
• Trapezoid graphs and their coloring
• Finding a maximum matching in a circular-arc graph
• Decomposable searching problems
• Algorithmic graph theory and perfect graphs
• Finding a maximum matching in a permutation graph
• Optimal scheduling for two-processor systems
• Fast Algorithms for Finding Nearest Common Ancestors
• A unifying look at data structures
• Quintary trees
• Optimal Sequencing of Two Equivalent Processors
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Efficient maximum matching algorithms for trapezoid graphs