Parameterized algorithms for multi-label periodic temporal graph realization

DOI10.1016/J.TCS.2025.115412MaRDI QIDQ6949551zbMATH OpenFDO

Authors Thomas Erlebach, Nils Morawietz, Petra Wolf

Publication date 1 August 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115412

zbMATH Keywords

almost-cliquedynamic networkfixed-parameter tractabilitykernelizationtemporal graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• Assigning times to minimise reachability in temporal graphs
• Computing independent sets in graphs with large girth
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• Distance matrix of a graph and its realizability
• Fundamentals of parameterized complexity
• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 1518742 (Why is no real title available?)
• Label-connected graphs and the gossip problem
• Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs
• Optimal listing of cycles and st-paths in undirected graphs
• Parameterized algorithms
• Temporal graph realization from fastest paths
• Temporal network optimization subject to connectivity constraints
• The complexity of computing optimum labelings for temporal connectivity
• The complexity of optimal design of temporally connected graphs
• The subspace flatness conjecture and faster integer programming

Cited in

(1)

• Temporal graph realization with bounded stretch

This page was built for publication: Parameterized algorithms for multi-label periodic temporal graph realization

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