Given a directed graph @math with arbitrary real-valued weights, the single source shortest-path problem (SSSP) asks for, given a source @math in @math , finding a shortest path from @math to each vertex @math in @math . A classical SSSP algorithm detects a negative cycle of @math or constructs a shortest-path tree (SPT) rooted at @math in @math time, where @math are the numbers of edges and vertices in @math respectively. In many practical applications, new constraints come from time to time and we need to update the SPT frequently. Given an SPT @math of @math , suppose the weight on a certain edge is modified. We show by rigorous proof that the well-known Ball-String algorithm for positively weighted graphs can be adapted to solve the dynamic SPT problem for directed graphs with arbitrary weights. Let @math be the number of vertices that are affected (i.e., vertices that have different distances from @math or different parents in the input and output SPTs) and @math the number of edges incident to an affected vertex. The adapted algorithms terminate in @math time, either detecting a negative cycle (only in the decremental case) or constructing a new SPT @math for the updated graph. We show by an example that the output SPT @math may have more than necessary edge changes to @math . To remedy this, we give a general method for transforming @math into an SPT with minimal edge changes in time @math provided that @math has no cycles with zero length.
Let @math be a weighted directed graph. For any edge @math in @math , we call @math , respectively, the and the of @math . The weight of an edge @math in @math is written as @math . In applications, these weights may denote distances between two cities or costs between two routers and thus are usually non-negative. The simple temporal problem @cite_16 can also be represented as a weighted directed graph, where each vertex @math represents a time point @math , and a weight @math on the edge from vertex @math to @math specifies that the time difference of @math and @math is upper bounded by @math , i.e., @math . Clearly, weights in this case may be negative.
@cite_16
2130182605
Abstract This paper extends network-based methods of constraint satisfaction to include continuous variables, thus providing a framework for processing temporal constraints. In this framework, called temporal constraint satisfaction problem (TCSP), variables represent time points and temporal information is represented by a set of unary and binary constraints, each specifying a set of permitted intervals. The unique feature of this framework lies in permitting the processing of metric information, namely, assessments of time differences between events. We present algorithms for performing the following reasoning tasks: finding all feasible times that a given event can occur, finding all possible relationships between two given events, and generating one or more scenarios consistent with the information provided. We distinguish between simple temporal problems (STPs) and general temporal problems, the former admitting at most one interval constraint on any pair of time points. We show that the STP, which subsumes the major part of Vilain and Kautz's point algebra, can be solved in polynomial time. For general TCSPs, we present a decomposition scheme that performs the three reasoning tasks considered, and introduce a variety of techniques for improving its efficiency. We also study the applicability of path consistency algorithms as preprocessing of temporal problems, demonstrate their termination and bound their complexities.