Temporal vertex cover with a sliding time window
Publication:2009637
DOI10.1016/j.jcss.2019.08.002zbMath1436.68219arXiv1802.07103OpenAlexW2963993884WikidataQ127350233 ScholiaQ127350233MaRDI QIDQ2009637
Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, Victor Zamaraev
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
approximation algorithmtemporal networksapproximation hardnessexponential time hypothesis (ETH)temporal vertex cover
Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Traveling salesman problems in temporal graphs
- Distributed algorithms for barrier coverage using relocatable sensors
- An efficient fixed-parameter algorithm for 3-hitting set
- Computing maximal cliques in link streams
- Some APX-completeness results for cubic graphs
- Which problems have strongly exponential complexity?
- Probabilistic distributed algorithms for energy efficient routing and tracking in wireless sensor networks
- Temporal network optimization subject to connectivity constraints
- Discovering recurring activity in temporal networks
- Sliding window temporal graph coloring
- Complexity of barrier coverage with relocatable sensors in the plane
- The complexity of optimal design of temporally connected graphs
- On temporal graph exploration
- DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
- Flooding Time of Edge-Markovian Evolving Graphs
- A threshold of ln n for approximating set cover
- Exploration of Periodically Varying Graphs
- On Problems as Hard as CNF-SAT
- Temporal Vertex Cover with a Sliding Time Window
- How fast can we reach a target vertex in stochastic temporal graphs
- Randomized Rumor Spreading in Dynamic Graphs
- COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
- Connectivity and inference problems for temporal networks
- The temporal explorer who returns to the base
- On the complexity of \(k\)-SAT