New approximation results on graph matching and related problems

DOI10.1007/3-540-59071-4_60zbMath1528.68302OpenAlexW1528077854MaRDI QIDQ6184382

Majid Sarrafzadeh, Yoji Kajitani, Jun Dong Cho

Publication date: 5 January 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59071-4_60

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Matching theory
• Approximation algorithms for weighted matching
• Matching structure and the matching lattice
• How well can a graph be n-colored?
• Worst case bounds for the Euclidean matching problem
• A still better performance guarantee for approximate graph coloring
• Some simplified NP-complete graph problems
• TWO THEOREMS IN GRAPH THEORY
• A survey of heuristics for the weighted matching problem
• Efficient dual simplex algorithms for the assignment problem
• Efficient algorithms for finding maximum matching in graphs
• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Approximation and intractability results for the maximum cut problem and its variants
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs