scientific article
From MaRDI portal
Publication:3140397
zbMath0801.68124MaRDI QIDQ3140397
Publication date: 29 November 1994
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
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)
Related Items (44)
Equivalence classes and conditional hardness in massively parallel computations ⋮ Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts ⋮ A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems ⋮ A branch-and-cut algorithm for the vehicle routing problem with two-dimensional loading constraints ⋮ Dual averaging with adaptive random projection for solving evolving distributed optimization problems ⋮ Recent developments in maximum flow algorithms ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Logical s-t Min-Cut Problem: An Extension to the Classic s-t Min-Cut Problem ⋮ 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 ⋮ Efficient algorithms for minimum range cut problems ⋮ Average Sensitivity of Graph Algorithms ⋮ Unnamed Item ⋮ Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions ⋮ Community detection in feature-rich networks using data recovery approach ⋮ Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs ⋮ Approximation algorithms for flexible graph connectivity ⋮ Unnamed Item ⋮ The Complexity of Boolean Surjective General-Valued CSPs ⋮ Multicriteria cuts and size-constrained \(k\)-cuts in hypergraphs ⋮ Faster cut sparsification of weighted graphs ⋮ A branch-and-cut algorithm for the soft-clustered vehicle-routing problem ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ Complexity of the min-max (regret) versions of min cut problems ⋮ A polynomial bound on the number of light cycles in an undirected graph ⋮ Computing girth and cogirth in perturbed graphic matroids ⋮ Multicriteria Cuts and Size-Constrained k-Cuts in Hypergraphs. ⋮ Optimal cuts in graphs and statistical mechanics ⋮ Most balanced minimum cuts ⋮ Community detection in node-attributed social networks: a survey ⋮ A simpler minimum spanning tree verification algorithm ⋮ Unnamed Item ⋮ A new contraction technique with applications to congruency-constrained cuts ⋮ A General Framework for Graph Sparsification ⋮ NP-hard and linear variants of hypergraph partitioning ⋮ Contracting a Planar Graph Efficiently ⋮ Social pressure in opinion dynamics ⋮ Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs ⋮ Fast Augmenting Paths by Random Sampling from Residual Graphs ⋮ On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes) ⋮ Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces ⋮ Maker-Breaker Games on Randomly Perturbed Graphs ⋮ Uniform-Circuit and Logarithmic-Space Approximations of Refined Combinatorial Optimization Problems ⋮ Hypergraph k-Cut for Fixed k in Deterministic Polynomial Time
This page was built for publication:
