Temporal vertex cover with a sliding time window
From MaRDI portal
Publication:2009637
approximation algorithmapproximation hardnessexponential time hypothesis (ETH)temporal networkstemporal vertex cover
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) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Abstract: Modern, inherently dynamic systems are usually characterized by a network structure, i.e. an underlying graph topology, which is subject to discrete changes over time. Given a static underlying graph , a temporal graph can be represented via an assignment of a set of integer time-labels to every edge of , indicating the discrete time steps when this edge is active. While most of the recent theoretical research on temporal graphs has focused on the notion of a temporal path and other "path-related" temporal notions, only few attempts have been made to investigate "non-path" temporal graph problems. In this paper, motivated by applications in sensor and in transportation networks, we introduce and study two natural temporal extensions of the classical problem Vertex Cover. In both cases we wish to minimize the total number of "vertex appearances" that are needed to "cover" the whole temporal graph. In our first problem, Temporal Vertex Cover, the aim is to cover every edge at least once during the lifetime of the temporal graph, where an edge can be covered by one of its endpoints, only at a time step when it is active. In our second, more pragmatic variation Sliding Window Temporal Vertex Cover, we are also given a natural number , and our aim is to cover every edge at least once at every consecutive time steps. We present a thorough investigation of the computational complexity and approximability of these two temporal covering problems. In particular, we provide strong hardness results, complemented by various approximation and exact algorithms. Some of our algorithms are polynomial-time, while others are asymptotically almost optimal under the Exponential Time Hypothesis (ETH) and other plausible complexity assumptions.
Recommendations
- Temporal vertex cover with a sliding time window
- Timeline cover in temporal graphs: exact and approximation algorithms
- Sliding window temporal graph coloring
- Vertex cover meets scheduling
- The lane covering problem with time windows
- On a cover time problem on a dynamic graph with steps at random times
- Assigning times to minimise reachability in temporal graphs
- Faster exploration of degree-bounded temporal graphs
- An introduction to temporal graphs: an algorithmic perspective
- An introduction to temporal graphs: an algorithmic perspective
Cites work
- A threshold of ln n for approximating set cover
- An efficient fixed-parameter algorithm for 3-hitting set
- Complexity of barrier coverage with relocatable sensors in the plane
- Computing maximal cliques in link streams
- COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
- Connectivity and inference problems for temporal networks
- Discovering recurring activity in temporal networks
- Distributed algorithms for barrier coverage using relocatable sensors
- DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
- Exploration of periodically varying graphs
- Flooding time of edge-Markovian evolving graphs
- How fast can we reach a target vertex in stochastic temporal graphs?
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1330032 (Why is no real title available?)
- scientific article; zbMATH DE number 1559541 (Why is no real title available?)
- Lower bounds based on the exponential time hypothesis
- On problems as hard as CNF-SAT
- On the complexity of k-SAT
- Probabilistic distributed algorithms for energy efficient routing and tracking in wireless sensor networks
- Randomized Rumor Spreading in Dynamic Graphs
- Sliding window temporal graph coloring
- Some APX-completeness results for cubic graphs
- Temporal network optimization subject to connectivity constraints
- Temporal vertex cover with a sliding time window
- The complexity of optimal design of temporally connected graphs
- The temporal explorer who returns to the base
- Traveling salesman problems in temporal graphs
- Which problems have strongly exponential complexity?
Cited in
(52)- The complexity of finding small separators in temporal graphs
- Sliding window temporal graph coloring
- A faster parameterized algorithm for temporal matching
- Multistage vertex cover
- Robustness: a new form of heredity motivated by dynamic networks
- Deleting edges to restrict the size of an epidemic in temporal networks
- Temporal matching on geometric graph data
- Parameterised temporal exploration problems
- An introduction to temporal graphs: an algorithmic perspective
- Temporal vertex cover with a sliding time window
- The complexity of finding small separators in temporal graphs
- As Time Goes By: Reflections on Treewidth for Temporal Graphs
- scientific article; zbMATH DE number 7559442 (Why is no real title available?)
- Deleting edges to restrict the size of an epidemic in temporal networks
- An introduction to temporal graphs: an algorithmic perspective
- Computing maximum matchings in temporal graphs.
- Multistage Vertex Cover
- The temporal explorer who returns to the base
- Feedback edge sets in temporal graphs
- Approximating multistage matching problems
- Approximating multistage matching problems
- Temporal interval cliques and independent sets
- The complexity of growing a graph
- Sharp Thresholds in Random Simple Temporal Graphs
- Disentangling the computational complexity of network untangling
- Untangling temporal graphs of bounded degree
- Computing maximum matchings in temporal graphs
- Payment scheduling in the interval debt model
- Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs
- Timeline cover in temporal graphs: exact and approximation algorithms
- A new temporal interpretation of cluster editing
- The complexity of computing optimum labelings for temporal connectivity
- The complexity of growing a graph
- Parity games on temporal graphs
- Cluster editing for multi-layer and temporal graphs
- Payment scheduling in the interval debt model
- Exploiting automorphisms of temporal graphs for fast exploration and rendezvous
- Multi-parameter analysis of finding minors and induced subgraphs in edge-periodic temporal graphs
- Temporal reachability dominating sets: contagion in temporal graphs
- An FPT algorithm for temporal graph untangling
- An FPT algorithm for timeline cover
- Exact and approximation algorithms for covering timeline in temporal graphs
- The complexity of transitively orienting temporal graphs
- How to reduce temporal cliques to find sparse spanners
- Temporal queries for dynamic temporal forests
- Partial temporal vertex cover with bounded activity intervals
- Temporal explorability games
- Temporal dominating set and temporal vertex cover under the lens of degree restrictions
- Timeline problems in temporal graphs: vertex cover vs. dominating set
- Parameterized temporal exploration problems
- Temporal unit interval independent sets
- 0-1 timed matching in bipartite temporal graphs
This page was built for publication: Temporal vertex cover with a sliding time window
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2009637)
