Quasi-Convex Matching Software

Description: This software implements the near linear time algorithms of Buss and Yianilos for solving a special class of bipartite weighted matching problems (assignment). Their paper "Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-convex Tours" appeared in SODA94, and will appear in Siam J. Computing.

The software was first described in UCSD Technical Report CS94-370 entitled "Solving the Minimum-Cost Matching Problem for Quasi-Convex Tours: An Efficient ANSI C Implementation", by the four authors above.

• FTP the software (tar/gzip)

• The distribution's README file

• See paper: Solving the Minimum-Cost Matching Problem for Quasi-Convex Tours: An Efficient ANSI C Implementation

• See also:
  • Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-convex Tours
  • The LikeIt Intelligent String Comparison Facility
  • Netrics Corporation: The commercial source of the world's most advanced intelligent data quality solutions -- industrial-strength machine intelligence and learning technology for the international medical information processing industry, and others for whom database quality and robust operation is critical.
  • The LikeIt Intelligent String Comparison Facility (Software)
  • A Bipartite Matching Approach to Approximate String Comparison and Search
  • Mulistage Intelligent String Comparison Method (patent pending)
  • Quasiconvex Bipartite Matching (patent pending)
  • The PF474 VLSI Chip
  • The Friendly Finder database utility
  • String comparator device system circuit and method (patent)
  • A dedicated compartor matches symbol strings fast and intelligently
  • String Comparator - A new tool for speech recognition
  • The application of a pattern matching algorithm to searching medical record text
  • The definition, computation, and application of symbol string similarity functions
  • PF474 Product Data Book

• My homepage ( Peter N. Yianilos )

• Coauthors:
  • Sam Buss
  • Kirk Kanzelberger
  • Dave Robinson