Approximation schemes for degree-restricted MST and red-blue separation problems

DOI10.1007/s00453-004-1103-4zbMath1082.68125OpenAlexW2116680937MaRDI QIDQ1762989

Sanjeev Arora, Kevin L. Chang

Publication date: 11 February 2005

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-004-1103-4

zbMATH Keywords

Approximation algorithmLow degreeDegree-Restricted Minimum Spanning Tree

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Computational aspects related to convexity (52B55) Approximation algorithms (68W25)

Related Items (11)

Plane bichromatic trees of low degree ⋮ Approximation schemes for node-weighted geometric Steiner tree problems ⋮ Exact and heuristic solutions for the prize‐collecting geometric enclosure problem ⋮ The Shortest Separating Cycle Problem ⋮ Polynomial area bounds for MST embeddings of trees ⋮ Planar Bichromatic Bottleneck Spanning Trees ⋮ Delineating boundaries for imprecise regions ⋮ Cooperative TSP ⋮ Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem ⋮ Degree-bounded minimum spanning trees ⋮ Planar bichromatic minimum spanning trees

This page was built for publication: Approximation schemes for degree-restricted MST and red-blue separation problems