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
1981859328 2943842266 1863224559 1997867453
This paper investigates a zero-sum game played on a weighted connected graph @math between two players, the tree player and the edge player. At each play, the tree player chooses a spanning tree @math and the edge player chooses an edge @math . The payoff to the edge player is @math , defined as follows: If @math lies in the tree @math then @math ; if @math does not lie in the tree then @math , where @math is the weight of edge @math and @math is the weight of the unique cycle formed when edge @math is added to the tree @math . The main result is that the value of the game on any @math -vertex graph is bounded above by @math . It is conjectured that the value of the game is @math . The game arises in connection with the @math -server problem on a road network; i.e., a metric space that can be represented as a multigraph @math in which each edge @math represents a road of length @math . It is shown that, if the value of the game on @math is @math , then there is a randomized strategy that achieves a competitive ratio of @math against any oblivious adversary. Thus, on any @math -vertex road network, there is a randomized algorithm for the @math -server problem that is @math competitive against oblivious adversaries. At the heart of the analysis of the game is an algorithm that provides an approximate solution for the simple network design problem. Specifically, for any @math -vertex weighted, connected multigraph, the algorithm constructs a spanning tree @math such that the average, over all edges @math , of @math is less than or equal to @math . This result has potential application to the design of communication networks. It also improves substantially known estimates concerning the existence of a sparse basis for the cycle space of a graph. Given a graph @math and a subset @math of terminals, a of @math is a tree that spans @math . In the vertex-weighted Steiner tree (VST) problem, each vertex is assigned a non-negative weight, and the goal is to compute a minimum weight Steiner tree of @math . We study a natural generalization of the VST problem motivated by multi-level graph construction, the (V-GSST), which can be stated as follows: given a graph @math and terminals @math , where each terminal @math requires a facility of a minimum grade of service @math , compute a Steiner tree @math by installing facilities on a subset of vertices, such that any two vertices requiring a certain grade of service are connected by a path in @math with the minimum grade of service or better. Facilities of higher grade are more costly than facilities of lower grade. Multi-level variants such as this one can be useful in network design problems where vertices may require facilities of varying priority. While similar problems have been studied in the edge-weighted case, they have not been studied as well in the more general vertex-weighted case. We first describe a simple heuristic for the V-GSST problem whose approximation ratio depends on @math , the number of grades of service. We then generalize the greedy algorithm of [Klein & Ravi, 1995] to show that the V-GSST problem admits a @math -approximation, where @math is the set of terminals requiring some facility. This result is surprising, as it shows that the (seemingly harder) multi-grade problem can be approximated as well as the VST problem, and that the approximation ratio does not depend on the number of grades of service. We study a natural extension of the Maximum Weight Independent Set Problem (MWIS), one of the most studied optimization problems in Graph algorithms. We are given a graph @math , a weight function @math , a budget function @math , and a positive integer @math . The weight (resp. budget) of a subset of vertices is the sum of weights (resp. budgets) of the vertices in the subset. A @math -budgeted independent set in @math is a subset of vertices, such that no pair of vertices in that subset are adjacent, and the budget of the subset is at most @math . The goal is to find a @math -budgeted independent set in @math such that its weight is maximum among all the @math -budgeted independent sets in @math . We refer to this problem as MWBIS. Being a generalization of MWIS, MWBIS also has several applications in Scheduling, Wireless networks and so on. Due to the hardness results implied from MWIS, we study the MWBIS problem in several special classes of graphs. We design exact algorithms for trees, forests, cycle graphs, and interval graphs. In unweighted case we design an approximation algorithm for @math -claw free graphs whose approximation ratio ( @math ) is competitive with the approximation ratio ( @math ) of MWIS (unweighted). Furthermore, we extend Baker's technique Baker83 to get a PTAS for MWBIS in planar graphs. A weighted directed graph G is a triple V, A, g where V, A is a directed graph and g is an arbitrary real-valued function defined on the arc set A. Let G be a strongly-connected, simple weighted directed graph. We say that G is max-balanced if for every nontrivial subset of the vertices W, the maximum weight over arcs leaving W equals the maximum weight over arcs entering W. We show that there exists a up to an additive constant unique potential pv for v ∈ V such that V, A, gp is max-balanced where gap = pu + ga-pv for a = u, v ∈ A. We describe an O|V|2|A| algorithm for computing p using an algorithm for computing the maximum cycle-mean of G. Finally, we apply our principal result to the similarity scaling of nonnegative matrices.