𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An O(pn2) algorithm for the p-median and related problems on tree graphs

✍ Scribed by Arie Tamir

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
402 KB
Volume
19
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

An improved algorithm for the minmax reg
An improved algorithm for the minmax regret median problem on a tree
✍ Igor Averbakh; Oded Berman πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 116 KB πŸ‘ 1 views

## Abstract We consider the 1‐median problem with uncertain weights for nodes. Specifically, for each node, only an interval estimate of its weight is known. It is required to find a β€œminmax regret” location, that is, to minimize the worst‐case loss in the objective function that may occur because

An O(n2) Divide-and-Conquer Algorithm fo
An O(n2) Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs
✍ A. Ehrenfeucht; H.N. Gabow; R.M. Mcconnell; S.J. Sullivan πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 526 KB

This paper presents a simple divide-and-conquer algorithm for computing the prime tree decomposition of a two-structure. The algorithm runs in \(O\left(n^{2}\right)\) time, when \(n\) is the number of nodes of the two-structure. A directed or undirected graph is a special case of a two-structure, an