Worst-case greedy matchings in the unitd-cube

DOI10.1002/net.3230200607zbMath0716.90096OpenAlexW2045021063MaRDI QIDQ3204344

Timothy Law Snyder, J. Michael Steele

Publication date: 1990

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.3230200607

zbMATH Keywords

asymptotic growth rate of the weightworst-case behavior of greedy matchings

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items

Computing the Ehrhart polynomial of a convex lattice polytope, Worst case asymptotics for some classical optimization problems, Worst-case minimum rectilinear Steiner trees in all dimensions

Cites Work

• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Paths, Trees, and Flowers
• Unnamed Item