scientific article; zbMATH DE number 437525
From MaRDI portal
Publication:3140397
zbMATH Open0801.68124MaRDI QIDQ3140397FDOQ3140397
Authors: David R. Karger 
Publication date: 29 November 1994
Title of this publication is not available (Why is that?)
Recommendations
randomized algorithmnetwork reliabilityCRCW PRAMweighted undirected graphs\({\mathcal R}{\mathcal N}{\mathcal C}\) algorithmapproximate min-cutsglobal min-cuts
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15)
Cited In (50)
- Maker-Breaker games on randomly perturbed graphs
- A branch-and-cut algorithm for the soft-clustered vehicle-routing problem
- Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
- Derandomization through approximation, an NC algorithm for minimum cuts
- Faster algorithms for next breakpoint and max value for parametric global minimum cuts
- A new contraction technique with applications to congruency-constrained cuts
- Efficient algorithms for minimum range cut problems
- Optimal cuts in graphs and statistical mechanics
- Most balanced minimum cuts
- Computing girth and cogirth in perturbed graphic matroids
- Community detection in node-attributed social networks: a survey
- A general framework for graph sparsification
- Equivalence classes and conditional hardness in massively parallel computations
- Computing exact minimum cuts without knowing the graph
- A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems
- Average Sensitivity of Graph Algorithms
- Deterministic enumeration of all minimum cut-sets and \(k\)-cut-sets in hypergraphs for fixed \(k\)
- Dual averaging with adaptive random projection for solving evolving distributed optimization problems
- A branch-and-cut algorithm for the vehicle routing problem with two-dimensional loading constraints
- Uniform-circuit and logarithmic-space approximations of refined combinatorial optimization problems
- Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs.
- Minimum cut in \(O(m \log^2 n)\) time
- A simpler minimum spanning tree verification algorithm
- Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions
- Algorithms for the ferromagnetic Potts model on expanders
- Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs
- Title not available (Why is that?)
- Complexity of the min-max (regret) versions of min cut problems
- Randomized contractions for multiobjective minimum cuts
- The Complexity of Boolean Surjective General-Valued CSPs
- Faster connectivity in low-rank hypergraphs via expander decomposition
- On the number of circuits in regular matroids (with connections to lattices and codes)
- A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms
- A 3/2-Approximation for the Metric Many-Visits Path TSP
- NP-hard and linear variants of hypergraph partitioning
- Fast augmenting paths by random sampling from residual graphs
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- Community detection in feature-rich networks using data recovery approach
- Randomized approximation schemes for cuts and flows in capacitated graphs
- A polynomial bound on the number of light cycles in an undirected graph
- Isolating a vertex via lattices: polytopes with totally unimodular faces
- A correctness certificate for the Stoer-Wagner min-cut algorithm
- Logical s-t Min-Cut Problem: An Extension to the Classic s-t Min-Cut Problem
- Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs
- Faster cut sparsification of weighted graphs
- Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
- Recent developments in maximum flow algorithms
- Approximation algorithms for flexible graph connectivity
- Contracting a planar graph efficiently
- Social pressure in opinion dynamics
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3140397)
