Temporal vertex cover with a sliding time window

DOI10.1016/j.jcss.2019.08.002zbMath1436.68219arXiv1802.07103MaRDI QIDQ2009637

George B. Mertzios, Paul G. Spirakis, Victor Zamaraev, Eleni C. Akrida

Publication date: 29 November 2019

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1802.07103

zbMATH Keywords

approximation algorithm; temporal networks; approximation hardness; exponential time hypothesis (ETH); temporal vertex cover

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

Uses Software

• cliques