𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A fast algorithm for minimum weight odd circuits and cuts in planar graphs

✍ Scribed by Adam N. Letchford; Nicholas A. Pearson

Publisher
Elsevier Science
Year
2005
Tongue
English
Weight
157 KB
Volume
33
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A Faster Algorithm for Finding the Minim
A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
✍ J.X. Hao; J.B. Orlin πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 995 KB

We consider the problem of finding the minimum capacity cut in a directed network \(G\) with \(n\) nodes. This problem has applications to network reliability and survivability and is useful in subroutines for other network optimization problems. One can use a maximum flow problem to find a minimum

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 branch and cut algorithm for the Stein
A branch and cut algorithm for the Steiner problem in graphs
✍ Lucena, A.; Beasley, J. E. πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 165 KB πŸ‘ 2 views

In this paper, we consider the Steiner problem in graphs, which is the problem of connecting together, at minimum cost, a number of vertices in an undirected graph with nonnegative edge costs. We use the formulation of this problem as a shortest spanning tree (SST) problem with additional constraint