Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs

Martin Weigt Alexander K. Hartmann

Published in: CoRR (2000)

Keyphrases

random graphs
optimal solution
dynamic programming
undirected graph
computational complexity
np hard
worst case
tree structure
bayesian networks
data structure
search space
probabilistic model
minimum weight