Temporal graph realization with bounded stretch

DOI10.1016/J.JCSS.2026.103814MaRDI QIDQ7262370zbMATH OpenFDO

Authors George B. Mertzios, Hendrik Molter, Nils Morawietz, P. G. Spirakis

Publication date 11 June 2026

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.2026.103814

zbMATH Keywords

fastest temporal pathgraph realizationperiodic temporal labelingstretchtemporal connectivitytemporal graph

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• A cop and robber game on edge-periodic temporal graphs
• Algorithmic meta-theorems for restrictions of treewidth
• Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs
• Assigning times to minimise reachability in temporal graphs
• Connectivity and inference problems for temporal networks
• Cops \& robber on periodic temporal graphs: characterization and improved bounds
• Deleting edges to restrict the size of an epidemic in temporal networks
• Distance matrix of a graph and its realizability
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 1432797 (Why is no real title available?)
• scientific article; zbMATH DE number 7559442 (Why is no real title available?)
• scientific article; zbMATH DE number 7724250 (Why is no real title available?)
• Label-connected graphs and the gossip problem
• Local search for string problems: brute-force is essentially optimal
• Local search: is brute-force avoidable?
• Lower-Stretch Spanning Trees
• Multi-parameter analysis of finding minors and induced subgraphs in edge-periodic temporal graphs
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• On the realization of a (p,s)-digraph with prescribed degrees
• Optimizing reachability sets in temporal graphs by delaying
• Parameterized algorithms
• Parameterized algorithms for multi-label periodic temporal graph realization
• Reducibility among combinatorial problems
• Reducing reachability in temporal graphs: towards a more realistic model of real-world spreading processes
• Searching the \(k\)-change neighborhood for TSP is W[1]-hard
• Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity
• Sparse temporal spanners with low stretch
• Temporal graph classes: a view through temporal separators
• Temporal graph realization from fastest paths
• Temporal network optimization subject to connectivity constraints
• Temporal reachability minimization: delaying vs. deleting
• The complexity of computing optimum labelings for temporal connectivity
• The complexity of finding small separators in temporal graphs
• The complexity of optimal design of temporally connected graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Using petal-decompositions to build a low stretch spanning tree

This page was built for publication: Temporal graph realization with bounded stretch

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