186,518 research outputs found
Nearly Linear Time Minimum Spanning Tree Maintenance for Transient Node Failures
No full textGiven a 2-node connected, real weighted, and undirected graph G=(V,E), with n nodes and m edges, and given a minimum spanning tree (MST) T=(V,ET) of G, we study the problem of finding, for every node v in V, a set of replacement edges which can be used for constructing an MST of G-v (i.e., the graph G deprived of v and all its incident edges). We show that this problem can be solved on a pointer machine in O(m ·alpha(m,n)) time and O(m) space, where alpha() is the functional inverse of Ackermann’s function. Our solution improves over the previously best known O(min{m ·alpha(n,n), m + n logn}) time bound, and allows us to close the gap existing with the fastest solution for the edge-removal version of the problem (i.e., that of finding, for every edge e in ET, a replacement edge which can be used for constructing an MST of G-e=(V,E\{e}). Our algorithm finds immediate application in maintaining MST-based communication networks undergoing temporary node failures. Moreover, in a distributed environment in which nodes are managed by selfish agents, it can be used to design an efficient, truthful mechanism for building an MST
Strongly polynomial-time truthful mechanisms in one shot
No full textAbstractOne of the main challenges in algorithmic mechanism design is to turn (existing) efficient algorithmic solutions into efficient truthful mechanisms. Building a truthful mechanism is indeed a difficult process since the underlying algorithm must obey certain “monotonicity” properties and suitable payment functions need to be computed (this task usually represents the bottleneck in the overall time complexity).We provide a general technique for building truthful mechanisms that provide optimal solutions in strongly polynomial time. We show that the entire mechanism can be obtained if one is able to express/write a strongly polynomial-time algorithm (for the corresponding optimization problem) as a “suitable combination” of simpler algorithms. This approach applies to a wide class of mechanism design graph problems, where each selfish agent corresponds to a weighted edge in a graph (the weight of the edge is the cost of using that edge). Our technique can be applied to several optimization problems which prior results cannot handle (e.g., MIN–MAX optimization problems).As an application, we design the first (strongly polynomial-time) truthful mechanism for the minimum diameter spanning tree problem, by obtaining it directly from an existing algorithm for solving this problem. For this non-utilitarian MIN–MAX problem, no truthful mechanism was known, even considering those running in exponential time (indeed, exact algorithms do not necessarily yield truthful mechanisms). Also, standard techniques for payment computations may result in a running time which is not polynomial in the size of the input graph. The overall running time of our mechanism, instead, is polynomial in the number n of nodes and m of edges, and it is only a factor O(nα(n,n)) away from the best known canonical centralized algorithm
Computational aspects of a 2-player Stackelberg shortest paths tree game
No full textLet a communication network be modelled by a directed graph G = (V,E) of n nodes and m edges. We consider a one-round two-player network pricing game, the Stackelberg Shortest Paths Tree (StackSPT) game. This is played on G, by assuming that edges in E are partitioned into two sets: a set E F of edges with a fixed positive real weight, and a set E P of edges that should be priced by one of the two players (the leader). Given a distinguished node r ∈ V, the StackSPT game is then as follows: the leader prices the edges in E P in such a way that he will maximize his revenue, knowing that the other player (the follower) will build a shortest paths tree of G rooted at r, say S(r), by running a publicly available algorithm. Quite naturally, for each edge selected in the solution, the leader’s revenue is assumed to be equal to the loaded price of an edge, namely the product of the edge price times the number of paths from r in S(r) that use it. First, we show that the problem of maximizing the leader’s revenue is NP-hard as soon as |E P | = Θ(n). Then, in search of an effective method for solving the problem when the size of E P is constant, we focus on the basic case in which |E P | = 2, and we provide an efficient O(n 2 logn) time algorithm. Afterwards, we generalize the approach to the case |E P | = k, and we show that it can be solved in polynomial time whenever k = O(1)
Finding the most vital node of a shortest path
No full textAbstractIn an undirected, 2-node connected graph G=(V,E) with positive real edge lengths, the distance between any two nodes r and s is the length of a shortest path between r and s in G. The removal of a node and its incident edges from G may increase the distance from r to s. A most vital node of a given shortest path from r to s is a node (other than r and s) whose removal from G results in the largest increase of the distance from r to s. In the past, the problem of finding a most vital node of a given shortest path has been studied because of its implications in network management, where it is important to know in advance which component failure will affect network efficiency the most. In this paper, we show that this problem can be solved in O(m+nlogn) time and O(m) space, where m and n denote the number of edges and the number of nodes in G
Locating Facilities on a Network to Minimize Their Average Service Radius
No full textLet G = (V, E) denote an undirected weighted graph of n nodes and m edges, and let U ⊆ V. The relative eccentricity of a node u ∈ U is the maximum distance in G between u and any other node of U, while the radius of U in G is the minimum relative eccentricity of all the nodes in U. Several facility location problems ask for partitioning the nodes of G so as to minimize some global optimization function of the radii of the subsets of the partition. Here, we focus on the problem of partitioning the nodes of G into exactly p ≥ 2 non-empty subsets, so as to minimize the sum of the subset radii, called the total radius of the partition. This problem can be easily seen to be NP-hard when p is part of the input, but when p is fixed it can be solved in polynomial time by reducing it to a similar partitioning problem. In this paper, we first present an efficient O(n3) time algorithm for the notable case p = 2, which improves the O(mn2 + n3 log n) running time obtainable by applying the aforementioned reduction. Then, in an effort of characterizing meaningful polynomial-time solvable instances of the problem when p is part of the input, we show that (i) when G is a tree, then the problem can be solved in O(n3p3) time, and (ii) when G has bounded treewidth h, then the problem can be solved in O(n4h+4p3) time
Finding All the Best Swaps of a Minimum Diameter Spanning Tree Under Transient Edge Failures
No full text- …
