Temporal Vertex Cover with a Sliding Time Window
DOI10.4230/LIPIcs.ICALP.2018.148zbMath1499.68243OpenAlexW3108502037MaRDI QIDQ5002837
Eleni C. Akrida, George B. Mertzios, Victor Zamaraev, Paul G. Spirakis
Publication date: 28 July 2021
Full work available at URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.148
approximation algorithmexponential time hypothesisAPX-hardnesstemporal networkstemporal 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 (5)
Uses Software
Cites Work
- Unnamed Item
- Traveling salesman problems in temporal graphs
- Distributed algorithms for barrier coverage using relocatable sensors
- Computing maximal cliques in link streams
- Which problems have strongly exponential complexity?
- Probabilistic distributed algorithms for energy efficient routing and tracking in wireless sensor networks
- Discovering recurring activity in temporal networks
- 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
- Exploration of Periodically Varying Graphs
- Randomized Rumor Spreading in Dynamic Graphs
- Temporal Network Optimization Subject to Connectivity Constraints
- COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
- Connectivity and inference problems for temporal networks
This page was built for publication: Temporal Vertex Cover with a Sliding Time Window
