An FPT algorithm for timeline cover

DOI10.1016/J.JCSS.2025.103679MaRDI QIDQ6939605zbMATH OpenFDO

Authors Riccardo Dondi, Manuel Lafond

Publication date 21 August 2025

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2025.103679

zbMATH Keywords

graph algorithmsparameterized complexitytemporal graphstemporal vertex cover

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parameterized complexity, tractability and kernelization (68Q27)

Cites work

• An FPT algorithm for temporal graph untangling
• Connectivity and inference problems for temporal networks
• Directed flow-augmentation
• Disentangling the computational complexity of network untangling
• Edge exploration of temporal graphs
• Flow-augmentation. III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
• Königsberg sightseeing: Eulerian walks in temporal graphs
• On temporal graph exploration
• Representative sets and irrelevant vertices: new tools for kernelization
• Temporal graph classes: a view through temporal separators
• 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

(1)

• Partial temporal vertex cover with bounded activity intervals

This page was built for publication: An FPT algorithm for timeline cover

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