The complexity of optimal design of temporally connected graphs
type: Item
instance of: scholarly article
title: The complexity of optimal design of temporally connected graphs
zbMATH Open document ID: 1379.68250
author: Eleni C. Akrida
author: Leszek Gąsieniec
author: George B. Mertzios
author: P. G. Spirakis
published in: Theory of Computing Systems
publication date: 2017-10-12T00:00:00Z
full work available at URL: https://arxiv.org/abs/1502.04579
full work available at URL: pmc6979514
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6790471
zbMATH Keywords: temporal graphs
zbMATH Keywords: network design
zbMATH Keywords: temporally connected
zbMATH Keywords: minimal graph
zbMATH Keywords: APX-hard
zbMATH Keywords: random input
Wikidata QID: Q59613292
MaRDI profile type: MaRDI publication profile
OpenAlex ID: W2461566632
arXiv ID: 1502.04579
cites work: Optimization, approximation, and complexity classes
cites work: On Temporally Connected Graphs of Small Cost
cites work: Computation in networks of passively mobile finite-state sensors
cites work: How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
cites work: Survivable Network Design with Degree or Order Constraints
cites work: Random graphs.
cites work: COMPUTING SHORTEST, FASTEST, AND FOREMOST JOURNEYS IN DYNAMIC NETWORKS
cites work: Flooding Time of Edge-Markovian Evolving Graphs
cites work: On the Complexity of Information Spreading in Dynamic Networks
cites work: Quickest Flows Over Time
cites work: Efficient continuous-time dynamic network flow algorithms
cites work: Distance labeling in graphs (extended abstract)
cites work: Online and Stochastic Survivable Network Design
cites work: Labeling Schemes for Flow and Connectivity
cites work: Connectivity and inference problems for temporal networks
cites work: One, two, three, many, or: Complexity aspects of dynamic network flows with dedicated arcs
cites work: Continuous and discrete flows over time
cites work: Distributed computation in dynamic networks
cites work: Additive Approximation for Bounded Degree Survivable Network Design
cites work: Temporal Network Optimization Subject to Connectivity Constraints
cites work: Mediated population protocols
cites work: Causality, influence, and computation in possibly disconnected synchronous dynamic networks
cites work: Probability and Computing
cites work: Graph colouring and the probabilistic method
cites work: Q4736826
DOI: 10.1007/S00224-017-9757-X
description: scientific article