Worst-case greedy matchings in the unitd-cube

DOI10.1002/NET.3230200607zbMATH Open0716.90096OpenAlexW2045021063MaRDI QIDQ3204344FDOQ3204344

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

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

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)

Cites Work

• Paths, Trees, and Flowers
• Title not available (Why is that?)
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs

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)