Temporal network optimization subject to connectivity constraints

DOI10.1007/s00453-018-0478-6zbMath1421.68139OpenAlexW2835349798MaRDI QIDQ1739101

Paul G. Spirakis, George B. Mertzios, Othon Michail

Publication date: 25 April 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-018-0478-6

zbMATH Keywords

optimizationgraph labelinghardness of approximationtemporal networkMenger's theoremtemporal connectivity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (24)

Distributed computation and reconfiguration in actively dynamic networks ⋮ Edge-Disjoint Branchings in Temporal Graphs ⋮ Mengerian temporal graphs revisited ⋮ Optimizing reachability sets in temporal graphs by delaying ⋮ Shortest Journeys in Directed Temporal Graphs ⋮ Mengerian graphs: characterization and recognition ⋮ Blackout-tolerant temporal spanners ⋮ The complexity of growing a graph ⋮ Blackout-tolerant temporal spanners ⋮ How fast can we reach a target vertex in stochastic temporal graphs? ⋮ Computing maximum matchings in temporal graphs ⋮ Multi-parameter analysis of finding minors and subgraphs in edge-periodic temporal graphs ⋮ Maximizing reachability in a temporal graph obtained by assigning starting times to a collection of walks ⋮ On short fastest paths in temporal graphs ⋮ Finding temporal paths under waiting time constraints ⋮ Edge-disjoint branchings in temporal digraphs ⋮ Finding Temporal Paths Under Waiting Time Constraints. ⋮ Temporal vertex cover with a sliding time window ⋮ Unnamed Item ⋮ Sliding window temporal graph coloring ⋮ Edge exploration of temporal graphs ⋮ Edge exploration of temporal graphs ⋮ On finding separators in temporal split and permutation graphs ⋮ Reducing reachability in temporal graphs: towards a more realistic model of real-world spreading processes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mediated population protocols
• Causality, influence, and computation in possibly disconnected synchronous dynamic networks
• Efficient continuous-time dynamic network flow algorithms
• Computation in networks of passively mobile finite-state sensors
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Distributed computation in dynamic networks
• Flooding time in edge-Markovian dynamic graphs
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• On Syntactic versus Computational Views of Approximability
• Labeling Schemes for Flow and Connectivity
• Fibonacci heaps and their uses in improved network optimization algorithms
• Temporal Network Optimization Subject to Connectivity Constraints
• Dijkstra's algorithm on-line
• COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
• On the Complexity of Information Spreading in Dynamic Networks
• An Introduction to Temporal Graphs: An Algorithmic Perspective^*
• Connectivity and inference problems for temporal networks
• Graph colouring and the probabilistic method

This page was built for publication: Temporal network optimization subject to connectivity constraints