Publication:3140397

zbMath0801.68124MaRDI QIDQ3140397

David R. Karger

Publication date: 29 November 1994

zbMATH Keywords

randomized algorithm; network reliability; CRCW PRAM; weighted undirected graphs; \({\mathcal R}{\mathcal N}{\mathcal C}\) algorithm; approximate min-cuts; global min-cuts

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

68M15: Reliability, testing and fault tolerance of networks and computer systems

68W15: Distributed algorithms

Related Items

Efficient algorithms for minimum range cut problems, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, Fast Augmenting Paths by Random Sampling from Residual Graphs, A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems, Dual averaging with adaptive random projection for solving evolving distributed optimization problems, A polynomial bound on the number of light cycles in an undirected graph, Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs, Complexity of the min-max (regret) versions of min cut problems, Optimal cuts in graphs and statistical mechanics, Most balanced minimum cuts, NP-hard and linear variants of hypergraph partitioning, Computing girth and cogirth in perturbed graphic matroids, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems