Worst-case greedy matchings in the unitd-cube

DOI10.1002/NET.3230200607MaRDI QIDQ3204344zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 4116586
• Greedy Matching on the Line
• scientific article; zbMATH DE number 4045188
• On the existence of weak greedy matching heuristics
• Inexpensive d‐dimensional matchings

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Paths, Trees, and Flowers

Cited in

(3)

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

This page was built for publication: Worst-case greedy matchings in the unitd-cube

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