Exact and approximation algorithms for covering timeline in temporal graphs

DOI10.1007/S10479-024-05993-8MaRDI QIDQ6945269zbMATH OpenFDO

Authors Riccardo Dondi, Alexandru Popa

Publication date 9 August 2025

Published in Annals of Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S10479-024-05993-8

zbMATH Keywords

approximation algorithmFPT algorithmNP-hard problemtemporal graphtimeline cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Cites work

• \(O(\sqrt{\log n})\) approximation algorithms for Min UnCut, Min 2CNF deletion, and directed cut problems
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• A better approximation ratio for the vertex cover problem
• An introduction to temporal graphs: an algorithmic perspective
• Approximation Algorithms for the Set Covering and Vertex Cover Problems
• Connectivity and inference problems for temporal networks
• Disentangling the computational complexity of network untangling
• Edge exploration of temporal graphs
• Königsberg sightseeing: Eulerian walks in temporal graphs
• On temporal graph exploration
• Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
• Raising the bar for \textsc{Vertex Cover}: fixed-parameter tractability above a higher guarantee
• Temporal graph classes: a view through temporal separators
• Temporal network theory
• Temporal vertex cover with a sliding time window
• The complexity of finding small separators in temporal graphs
• The network-untangling problem: from interactions to activity timelines
• The temporal explorer who returns to the base
• Timeline cover in temporal graphs: exact and approximation algorithms
• Untangling temporal graphs of bounded degree

Cited in

(2)

• Partial temporal vertex cover with bounded activity intervals
• Temporal dominating set and temporal vertex cover under the lens of degree restrictions

This page was built for publication: Exact and approximation algorithms for covering timeline in temporal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6945269)