Efficient maximum matching algorithms for trapezoid graphs

DOI10.5614/EJGTA.2017.5.1.2MaRDI QIDQ5006595zbMATH OpenOpenAlexFDO

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

Publication date 16 August 2021

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

Copyright license Creative Commons Attribution-ShareAlike 4.0 International

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

zbMATH Keywords

trapezoid graphsmaximum matching

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)

Recommendations

• Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
• Trapezoid graphs and generalizations, geometry and algorithms
• Trapezoid graphs and generalizations, geometry and algorithms
• New results on induced matchings
• An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs

Cites work

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

Cited in

(7)

• Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs
• Efficient algorithm for the vertex connectivity of trapezoid graphs
• Trapezoid graphs and generalizations, geometry and algorithms
• An efficient algorithm to solve connectivity problem on trapezoid graphs
• An Efficient Algorithm to Generate all Maximal Cliques on Trapezoid Graphs
• AN IMPROVED PARALLEL ALGORITHM FOR A GEOMETRIC MATCHING PROBLEM WITH APPLICATION TO TRAPEZOID GRAPHS
• An efficient implementation of the Gale and Shapley ``propose-and-reject algorithm

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

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