Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree Problems.

Chandra Chekuri Kent Quanrud Manuel R. Torres

Published in: APPROX-RANDOM (2021)

Keyphrases

approximation algorithms
minimum cost
spanning tree
vertex cover
special case
undirected graph
randomized algorithms
np hard
np hardness
minimum spanning tree
approximation schemes
decision problems
primal dual
optimization problems
minimum weight
minimum spanning trees
data management
graphical models
worst case