𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A strongly polynomial algorithm for the inverse shortest arborescence problem

✍ Scribed by Hu Zhiquan; Liu Zhenhong

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
909 KB
Volume
82
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper an inverse problem of the weighted shortest arborescence problem is discussed.

That is. given a directed graph G and a set of nonnegative costs on its arcs. we need to modify those costs as little as possible to ensure that T, a given (.I-arborescence of G, is the shortest one. It is found that only the cost of T needs modifying. An O(rz") combinatorial algorithm is then proposed. This algorithm also gives an optimal solution to the inverse weighted shortest path problem.

πŸ“œ SIMILAR VOLUMES

A strongly polynomial algorithm for the
A strongly polynomial algorithm for the uniform balanced network flow problem
✍ Maria Grazia ScutellΓ‘ πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 565 KB

## Several balanced optimization problems have been analysed in the literature. Here, the balanced network flow problem in the uniform case is studied, and it is shown that it can be solved by the Newton's approach in O(n' log3 n) max-flow computations. The key of the proof is an extension of Rad

A branch-and-cut algorithm for the resou
A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem
✍ Fischetti, Matteo; Vigo, Daniele πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 150 KB πŸ‘ 2 views

In this paper, we present a branch-and-cut algorithm for the exact solution of an NP-hard extension of the well-known Minimum-Weight Arborescence (MWA) problem, in which resource constraints for each node are considered. This Resource-Constrained Minimum-Weight Arborescence (RMWA) problem arises, e.

A Polynomial-time Algorithm for the Bist
A Polynomial-time Algorithm for the Bistable Roommates Problem
✍ Jay Sethuraman; Chung-Piaw Teo πŸ“‚ Article πŸ“… 2001 πŸ› Elsevier Science 🌐 English βš– 127 KB

In a recent paper, Weems introduced the bistable matching problem, and asked if a polynomial-time algorithm exists to decide the feasibility of the bistable roommates problem. We resolve this question in the affirmative using linear programming. In addition, we show that several (old and new) result