2013 | OriginalPaper | Buchkapitel
Temporal Network Optimization Subject to Connectivity Constraints
verfasst von : George B. Mertzios, Othon Michail, Ioannis Chatzigiannakis, Paul G. Spirakis
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this work we consider
temporal networks
, i.e. networks defined by a
labeling
λ
assigning to each edge of an
underlying graph
G
a set of
discrete
time-labels. The labels of an edge, which are natural numbers, indicate the discrete time moments at which the edge is available. We focus on
path problems
of temporal networks. In particular, we consider
time-respecting
paths, i.e. paths whose edges are assigned by
λ
a strictly increasing sequence of labels. We begin by giving two efficient algorithms for computing shortest time-respecting paths on a temporal network. We then prove that there is a
natural analogue of Menger’s theorem
holding for arbitrary temporal networks. Finally, we propose two
cost minimization parameters
for temporal network design. One is the
temporality
of
G
, in which the goal is to minimize the maximum number of labels of an edge, and the other is the
temporal cost
of
G
, in which the goal is to minimize the total number of labels used. Optimization of these parameters is performed subject to some
connectivity constraint
. We prove several lower and upper bounds for the temporality and the temporal cost of some very basic graph families such as rings, directed acyclic graphs, and trees.