๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Revisiting a simple algorithm for the planar multiterminal cut problem

โœ Scribed by Kevin K.H. Cheung; Kyle Harvey

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
315 KB
Volume
38
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A Simple Algorithm for the Planar Multiw
A Simple Algorithm for the Planar Multiway Cut Problem
โœ Wei-Chang Yeh ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 95 KB

The traditional min-cut problem involves finding a cut with minimum weight between two specified vertices. The planar multiway cut problem is a NP-hard generalization of the min-cut problem. It involves separating a weighted planar graph with k specified vertices into k components such that the tota

A Simple Parallel Algorithm for the Sing
A Simple Parallel Algorithm for the Single-Source Shortest Path Problem on Planar Digraphs
โœ Jesper L. Trรคff; Christos D. Zaroliagis ๐Ÿ“‚ Article ๐Ÿ“… 2000 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 216 KB

We present a simple parallel algorithm for the single-source shortest path problem in planar digraphs with nonnegative real edge weights. The algorithm runs on the EREW PRAM model of parallel computation in O((n 2= +n 1&= ) log n) time, performing O(n 1+= log n) work for any 0<=<1ร‚2. The strength of

A branch-and-cut algorithm for the preem
A branch-and-cut algorithm for the preemptive swapping problem
โœ Charles Bordenave; Michel Gendreau; G. Laporte ๐Ÿ“‚ Article ๐Ÿ“… 2011 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 247 KB ๐Ÿ‘ 1 views

## Abstract In the swapping problem (SP), every vertex of a complete graph may supply and demand an object of a known type. A vehicle of unit capacity starting and ending its tour at an arbitrary vertex is available for carrying objects of given types between vertices. The SP consists of determinin