Fully-dynamic min-cut
type: Item
instance of: scholarly article
title: Fully-dynamic min-cut
zbMATH Open document ID: 1135.68024
author: Thorup Mikkel
published in: Combinatorica
publication date: 2008-05-29T00:00:00Z
review text: The paper is about the problem of maintaining a min-cut of a fully-dynamic (i.e. the graph may be updated by insertion and deletion of edges) graph. Its main technical contribution consists of a much more detailed analysis of a greedy tree packing technique, previously used by Karger. Namely, it is shown that in a graph with polylogarithmic edge connectivity an appropriately large greedy tree packing contains a tree crossing some min-cut only once. As the approach allows implementation in dynamic fashion, putting the results together yields the desired result -- deterministic maintenance of min-cuts of up to polylogarithmnic size and randomized maintenance of near-minimal cuts of arbitrary size.
reviewed by: Jozef Vyskoč
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5281488
zbMATH Keywords: graph
zbMATH Keywords: dynamic graph algorithm
zbMATH Keywords: min-cut
zbMATH Keywords: edge connectivity
zbMATH Keywords: greedy tree packing
MaRDI profile type: Publication
full work available at URL: s00493-007-0045-2
OpenAlex ID: W2611854190
DOI: 10.1007/S00493-007-0045-2
Recommended article: Fully-dynamic min-cut
Recommended article: Minimum Range Balanced Cuts via Dynamic Subset Sums
Recommended article: Deterministic mincut in almost-linear time
Recommended article: Minimum cuts in parametric networks
Recommended article: Structural and algorithmic properties for parametric minimum cuts
Recommended article: Q5874530
Recommended article: A faster parametric minimum-cut algorithm
Recommended article: Q4228454
Recommended article: Finding Robust Minimum Cuts
Recommended article: Practical Minimum Cut Algorithms
description: scientific article; zbMATH DE number 5281488