An improved approximation algorithm of MULTIWAY CUT.
type: Item
instance of: scholarly article
title: An improved approximation algorithm of MULTIWAY CUT.
zbMATH Open document ID: 0986.90043
author: Gruia Calinescu
author: Yuval Rabani
author: Howard Karloff
published in: Journal of Computer and System Sciences
publication date: 2000-11-21T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 1497377
zbMATH Keywords: undirected graph
zbMATH Keywords: MULTIWAY CUT of minimum cost
zbMATH Keywords: linear programming relaxation
MaRDI profile type: Publication
full work available at URL: jcss.1999.1687
OpenAlex ID: W3009415557
cites work: Q3056948
cites work: Q4234075
cites work: Q4230322
cites work: Nonlinear formulations and improved randomized approximation algorithms for multicut problems
cites work: Extended formulations for the \(A\)-cut problem
cites work: On the multiway cut polyhedron
cites work: Q4035360
cites work: The Complexity of Multiterminal Cuts
cites work: On weighted multiway cuts in trees
cites work: Q5514188
cites work: Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
cites work: Geometric algorithms and combinatorial optimization.
cites work: An $O ( | V |^2 )$ Algorithm for the Planar 3-Cut Problem
cites work: Q5595961
cites work: A new approach to the minimum cut problem
cites work: Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
cites work: Q4840777
cites work: Multiprocessor Scheduling with the Aid of Network Flow Algorithms
DOI: 10.1006/JCSS.1999.1687
Recommended article: Q4542519
Recommended article: Q3014297
Recommended article: Approximation algorithms for feasible cut and multicut problems
Recommended article: Q5743427
Recommended article: A local search approximation algorithm for the multiway cut problem
Recommended article: A simple algorithm for the multiway cut problem
Recommended article: An improved parameterized algorithm for the minimum node multiway cut problem
Recommended article: An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
Recommended article: A 2-approximation algorithm for the directed multiway cut problem
Recommended article: Simple and improved parameterized algorithms for multiterminal cuts
description: scientific article; zbMATH DE number 1497377