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

DOI10.1137/S0097539794267243zbMath0913.05086MaRDI QIDQ4388868

Peter N. Yianilos, Samuel R. Buss

Publication date: 10 May 1998

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

zbMATH Keywords

convexitymatchingtime complexityassignment problemcomputational geometrylinear timestring comparisonMonge propertybipartite weighted matchingquadrangle inequalityconcave penalty functionsymmetric cost function

Mathematics Subject Classification ID

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

Related Items (5)

New variants of perfect non-crossing matchings ⋮ ASSIGNMENT QUERY AND ITS IMPLEMENTATION IN MOVING OBJECT DATABASES ⋮ String shuffle: circuits and graphs ⋮ Planar graphs, negative weight edges, shortest paths, and near linear time ⋮ Optimal point movement for covering circular regions

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