scientific article; zbMATH DE number 1775387

zbMath1028.68220MaRDI QIDQ4542519

Yuval Rabani, Gruia Călinescu, Howard J. Karloff

Publication date: 1 August 2002

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

undirected graphMULTIWAY CUT

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (19)

Extended cuts ⋮ Solving \((k-1)\)-stable instances of \texttt{k-terminal cut} with isolating cuts ⋮ On the minimum cut separator problem ⋮ Experimental evaluation of a local search approximation algorithm for the multiway cut problem ⋮ A lower bound of \(8/(7+\frac{1}{k-1})\) on the integrality ratio of the Călinescu-Karloff-Rabani relaxation for multiway cut ⋮ The multi-multiway cut problem ⋮ Geometric rounding: A dependent randomized rounding scheme ⋮ A local search approximation algorithm for the multiway cut problem ⋮ New geometry-inspired relaxations and algorithms for the metric Steiner tree problem ⋮ Mixed-case community detection problem in social networks: algorithms and analysis ⋮ Approximation Algorithms for CSPs ⋮ Lifting Methods for Manifold-Valued Variational Problems ⋮ Optimal 3-terminal cuts and linear programming ⋮ Minimal multicut and maximal integer multiflow: a survey ⋮ Unnamed Item ⋮ Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program ⋮ Approximation algorithms for vertex happiness ⋮ Isolation branching: a branch and bound algorithm for the \(k \)-terminal cut problem ⋮ Unnamed Item

This page was built for publication: