Linear and O(n log n) Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours.

Samuel R. Buss Peter N. Yianilos

Published in: SODA (1994)

Keyphrases

minimum cost
computational complexity
minimum cost flow
worst case
approximation algorithms
spanning tree
np hard
optimization problems
network flow
learning algorithm
network simplex algorithm
quasiconvex
capacity constraints
piecewise linear
finite number
pattern matching
lower bound