A Linear-Time and Linear-Space Algorithm for the Minimum Vertex Cover Problem on Giant Graphs.

Hong Xu T. K. Satish Kumar Sven Koenig

Published in: SOCS (2017)

Keyphrases

linear space
computational complexity
worst case
search space
np hard
dynamic programming
space efficient
high accuracy
optimal solution
distance function
probabilistic model
simulated annealing
shortest path
matching algorithm
belief propagation
memory space
external memory