Temporal vertex cover with a sliding time window

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

zbMATH Keywords

approximation algorithmtemporal networksapproximation hardnessexponential time hypothesis (ETH)temporal vertex cover

Mathematics Subject Classification ID

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 (22)

As Time Goes By: Reflections on Treewidth for Temporal Graphs ⋮ Multistage vertex cover ⋮ Deleting edges to restrict the size of an epidemic in temporal networks ⋮ 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 ⋮ Temporal matching on geometric graph data ⋮ Parameterised temporal exploration problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Robustness: a new form of heredity motivated by dynamic networks ⋮ Sliding window temporal graph coloring ⋮ The temporal explorer who returns to the base ⋮ Approximating multistage matching problems ⋮ Approximating multistage matching problems ⋮ A faster parameterized algorithm for temporal matching

Uses Software

• cliques

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

This page was built for publication: Temporal vertex cover with a sliding time window