Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality

DOI10.1007/3-540-57899-4_37zbMath1528.68294OpenAlexW1519180672MaRDI QIDQ6184389

Alan M. Gibbons, Unnamed Author, Somasundaram Ravindran

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-57899-4_37

zbMATH Keywords

matchingparallel algorithmsapproximation algorithms

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved parallel algorithm for maximal matching
• Matching is as easy as matrix inversion
• Constructing a perfect matching is in random NC
• Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs
• Linear-time approximation algorithms for finding the minimum-weight perfect matching on a plane
• Parallel computation and conflicts in memory access
• Improved processor bounds for combinatorial problems in RNC
• Heuristic matching for graphs satisfying the triangle inequality
• On a Greedy Heuristic for Complete Matching
• An O(logn) parallel connectivity algorithm
• Fast Connected Components Algorithms for the EREW PRAM
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices

This page was built for publication: Approximating minimum weight perfect matchings for complete graphs satisfying the triangle inequality