scientific article; zbMATH DE number 1003236

MaRDI QIDQ4335196zbMATH OpenFDO

Authors Peter N. Yianilos, Samuel R. Buss

Publication date 1 June 1997

zbMATH Keywords

assignmentbipartite weighted matchingcomputational geometryconcave penalty functionconvexityedge costsEuclidean distancelinear-time algorithmmatchingminimum-cost matchingMonge propertyquadrangle inequalitystring comparison

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours
• Efficient Minimum Cost Matching and Transportation Using the Quadrangle Inequality
• Faster scaling algorithms for general graph matching problems

Cited in

(13)

• A linear time algorithm for a matching problem on the circle
• \(n\)-Tokyoites' loop-line commuter problem
• Perspectives of Monge properties in optimization
• Minimum cost b-matching problems with neighborhoods
• Unshuffling a square is NP-hard
• Approximating the Minimum Tour Cover with a Compact Linear Program
• Bipartite graph matching for points on a line or a circle
• A generalization of Hungarian method and Hall's theorem with applications in wireless sensor networks
• An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications
• Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours
• Geometric algorithms for the minimum cost assignment problem
• Necklaces, convolutions, and \(X+Y\)
• Necklaces, Convolutions, and X + Y

This page was built for publication:

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