Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams.

Jacques Dark Christian Konrad

Published in: Computational Complexity Conference (2020)

Keyphrases

vertex cover
lower bound
approximation algorithms
worst case
optimality criterion
upper bound
constant factor
optimal solution
np hard
planar graphs
dynamic graph
data streams
dynamic programming
objective function
evaluation function
linear programming relaxation