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 (49)
- A branch-and-cut algorithm for the soft-clustered vehicle-routing problem
- Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs
- 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
- Title not available (Why is that?)
- Equivalence classes and conditional hardness in massively parallel computations
- On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)
- A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems
- Average Sensitivity of Graph Algorithms
- Fast Augmenting Paths by Random Sampling from Residual Graphs
- 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
- Title not available (Why is that?)
- A branch-and-cut algorithm for the vehicle routing problem with two-dimensional loading constraints
- Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
- Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs.
- Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces
- 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
- Contracting a Planar Graph Efficiently
- 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
- Maker-Breaker Games on Randomly Perturbed Graphs
- The Complexity of Boolean Surjective General-Valued CSPs
- Faster connectivity in low-rank hypergraphs via expander decomposition
- A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms
- Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts
- Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems
- A 3/2-Approximation for the Metric Many-Visits Path TSP
- NP-hard and linear variants of hypergraph partitioning
- Community detection in feature-rich networks using data recovery approach
- A polynomial bound on the number of light cycles in an undirected graph
- 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
- Title not available (Why is that?)
- Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
- Recent developments in maximum flow algorithms
- Approximation algorithms for flexible graph connectivity
- 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)
