The Complexity of Temporal Vertex Cover in Small-Degree Graphs.

Thekla Hamm Nina Klobas George B. Mertzios Paul G. Spirakis

Published in: AAAI (2022)

Keyphrases

vertex cover
planar graphs
brute force search
approximation algorithms
worst case
probabilistic model
graph structure
space complexity
optimality criterion
social networks
precedence constraints
polynomial time approximation