Timeline problems in temporal graphs: vertex cover vs. dominating set

DOI10.4230/LIPICS.IPEC.2025.12MaRDI QIDQ7356334zbMATH OpenFDO

Authors Anton Herrmann, Christian Komusiewicz, Nils Morawietz, Frank Sommer

Publication date 23 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.IPEC.2025.12

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Algorithms in computer science (68Wxx)

Cites work

• A constructive proof of Vizing's theorem
• An FPT algorithm for timeline cover
• Color-coding
• Disentangling the computational complexity of network untangling
• Distance to transitivity: new parameters for taming reachability in temporal graphs
• Edge exploration of temporal graphs
• Exact and approximation algorithms for covering timeline in temporal graphs
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 1261820 (Why is no real title available?)
• Making the interval membership width of temporal graphs connected and bidirectional
• Multistage vertex cover
• On an estimate of the chromatic class of a \(p\)-graph
• Parameterized algorithms
• Structural parameters for dense temporal graphs
• Temporal reachability dominating sets: contagion in temporal graphs
• Temporal vertex cover with a sliding time window
• The h-Index of a Graph and its Application to Dynamic Subgraph Statistics
• The network-untangling problem: from interactions to activity timelines
• Untangling temporal graphs of bounded degree

This page was built for publication: Timeline problems in temporal graphs: vertex cover vs. dominating set

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