Temporal vertex cover with a sliding time window
type: Item
instance of: scholarly article
title: Temporal vertex cover with a sliding time window
zbMATH Open document ID: 1436.68219
author: Eleni C. Akrida
author: George B. Mertzios
author: P. G. Spirakis
author: Victor Zamaraev
published in: Journal of Computer and System Sciences
publication date: 2019-11-29T00:00:00Z
full work available at URL: https://arxiv.org/abs/1802.07103
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2018/9152/
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 7138696
zbMATH Keywords: temporal networks
zbMATH Keywords: temporal vertex cover
zbMATH Keywords: exponential time hypothesis (ETH)
zbMATH Keywords: approximation algorithm
zbMATH Keywords: approximation hardness
describes a project that uses: cliques
MaRDI profile type: Publication
OpenAlex ID: W2963993884
arXiv ID: 1802.07103
cites work: DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
cites work: The complexity of optimal design of temporally connected graphs
cites work: How fast can we reach a target vertex in stochastic temporal graphs
cites work: The temporal explorer who returns to the base
cites work: Temporal Vertex Cover with a Sliding Time Window
cites work: Some APX-completeness results for cubic graphs
cites work: COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
cites work: Q4526990
cites work: Flooding Time of Edge-Markovian Evolving Graphs
cites work: On Problems as Hard as CNF-SAT
cites work: Complexity of barrier coverage with relocatable sensors in the plane
cites work: On temporal graph exploration
cites work: A threshold of ln n for approximating set cover
cites work: Exploration of Periodically Varying Graphs
cites work: Q4198056
cites work: Randomized Rumor Spreading in Dynamic Graphs
cites work: Distributed algorithms for barrier coverage using relocatable sensors
cites work: On the complexity of \(k\)-SAT
cites work: Which problems have strongly exponential complexity?
cites work: Connectivity and inference problems for temporal networks
cites work: Discovering recurring activity in temporal networks
cites work: Q4904144
cites work: Temporal network optimization subject to connectivity constraints
cites work: Sliding window temporal graph coloring
cites work: Traveling salesman problems in temporal graphs
cites work: An efficient fixed-parameter algorithm for 3-hitting set
cites work: Probabilistic distributed algorithms for energy efficient routing and tracking in wireless sensor networks
cites work: Q4258215
cites work: Computing maximal cliques in link streams
Wikidata QID: Q127350233
DOI: 10.1016/J.JCSS.2019.08.002
Recommended article: Temporal Vertex Cover with a Sliding Time Window
Recommended article: Timeline cover in temporal graphs: exact and approximation algorithms
Recommended article: Sliding window temporal graph coloring
Recommended article: Vertex cover meets scheduling
Recommended article: The lane covering problem with time windows
Recommended article: On a cover time problem on a dynamic graph with steps at random times
Recommended article: Assigning times to minimise reachability in temporal graphs
Recommended article: Q5005137
Recommended article: An Introduction to Temporal Graphs: An Algorithmic Perspective
Recommended article: An Introduction to Temporal Graphs: An Algorithmic Perspective*
description: scientific article