𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Approximation Algorithms for Steiner and Directed Multicuts

✍ Scribed by Philip N Klein; Serge A Plotkin; Satish Rao; Éva Tardos

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
277 KB
Volume
22
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we consider the Steiner multicut problem. This is a generalization of the minimum multicut problem where instead of separating node pairs, the goal is to find a minimum weight set of edges that separates all given sets of nodes. A set is considered separated if it is not contained in a single connected component.

Ž 3 Ž .. We show an O log kt approximation algorithm for the Steiner multicut problem, where k is the number of sets and t is the maximum cardinality of a set. This Ž . improves the O t log k bound that easily follows from the previously known multicut results. We also consider an extension of multicuts to directed case, namely the problem of finding a minimum-weight set of edges whose removal

📜 SIMILAR VOLUMES

Approximation Algorithms for Directed St
Approximation Algorithms for Directed Steiner Problems
✍ Moses Charikar; Chandra Chekuri; To-yat Cheung; Zuo Dai; Ashish Goel; Sudipto Gu 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 181 KB

We give the first non-trivial approximation algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed graphs. These problems have several applications in network design and multicast routing.

Approximation algorithm for the group St
Approximation algorithm for the group Steiner network problem
✍ Michal Penn; Stas Rozenfeld 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 143 KB

## Abstract In this article we study the __group Steiner network__ problem, which is defined in the following way. Given a graph __G__ = (__V,E__), a partition of its vertices into K groups and connectivity requirements between the different groups, the aim is to find simultaneously a set of repres

A Polylogarithmic Approximation Algorith
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
✍ Naveen Garg; Goran Konjevod; R. Ravi 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 130 KB

The group Steiner tree problem is a generalization of the Steiner tree problem where we are given several subsets (groups) of vertices in a weighted graph, and the goal is to find a minimum-weight connected subgraph containing at least one vertex from each group.The problem was introduced by Reich a

Direct algorithm for the random-phase ap
Direct algorithm for the random-phase approximation
✍ V. G. Zakrzewski; O. Dolgounitcheva; J. V. Ortiz 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 525 KB

An algorithm for calculating excitation energies and transition moments in the randomphase approximation (RPA) of the polarization propagator is presented. The algorithm includes direct solution of the RPA eigenvalue problem and direct evaluation of products of superoperator Hamiltonian matrices wit