Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours

DOI10.1137/S0097539794267243MaRDI QIDQ4388868zbMATH OpenFDO

Authors Peter N. Yianilos, Samuel R. Buss

Publication date 10 May 1998

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539794267243

zbMATH Keywords

assignment problembipartite weighted matchingcomputational geometryconcave penalty functionconvexitylinear timematchingMonge propertyquadrangle inequalitystring comparisonsymmetric cost functiontime complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Other problems of combinatorial convexity (52A37) Graph theory (including graph drawing) in computer science (68R10) Computing methodologies for text processing; mathematical typography (68U15) Parallel algorithms in computer science (68W10) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 1003236
• Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality
• Faster scaling algorithms for general graph matching problems

Cited in

(9)

• String shuffle: circuits and graphs
• Minimum cost b-matching problems with neighborhoods
• Planar graphs, negative weight edges, shortest paths, and near linear time
• Approximating the Minimum Tour Cover with a Compact Linear Program
• ASSIGNMENT QUERY AND ITS IMPLEMENTATION IN MOVING OBJECT DATABASES
• An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications
• scientific article; zbMATH DE number 1003236 (Why is no real title available?)
• Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality
• New variants of perfect non-crossing matchings

This page was built for publication: Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours

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