Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
From MaRDI portal
Publication:3989010
DOI10.1137/0405004zbMath0754.05062OpenAlexW2035228443MaRDI QIDQ3989010
Toshihide Ibaraki, Hiroshi Nagamochi
Publication date: 28 June 1992
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0405004
Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)
Related Items
Computing maximum mean cuts, Minimum Cuts in Surface Graphs, Cache Oblivious Minimum Cut, Faster Algorithms for Next Breakpoint and Max Value for Parametric Global Minimum Cuts, Realizing symmetric set functions as hypergraph cut capacity, A note on minimizing submodular functions, A min-cut approach to functional regionalization, with a case study of the Italian local labour market areas, Recent developments in maximum flow algorithms, Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs, Minimum degree orderings, Efficient algorithms for the problems of enumerating cuts by non-decreasing weights, Some inverse min-max network problems under weighted \(l_1\) ans \(l_{\infty}\) norms with bound constraints on changes, Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs, Sparse connectivity certificates via MA orderings in graphs, Minimum Cuts and Sparsification in Hypergraphs, Faster connectivity in low-rank hypergraphs via expander decomposition, Graph searches and their end vertices, A network flow model of group technology, A new unifying heuristic algorithm for the undirected minimum cut problems using minimum range cut algorithms, Efficient computation of implicit representations of sparse graphs, Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Inverse maximum capacity problems, A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem, Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties, Minimum Cut and Minimum k -Cut in Hypergraphs via Branching Contractions, Characterizing redundant rigidity and redundant global rigidity of body-hinge graphs, Complexity of (arc)-connectivity problems involving arc-reversals or deorientations, Strongly polynomial bounds for multiobjective and parametric global minimum cuts in graphs and hypergraphs, Efficient Algorithms for the k Smallest Cuts Enumeration, Unnamed Item, Generalized cut trees for edge-connectivity, Tight approximation ratio of a general greedy splitting algorithm for the minimum \(k\)-way cut problem, A note on the minimization of symmetric and general submodular functions, Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths, Faster cut sparsification of weighted graphs, On the cut polyhedron., Practical Minimum Cut Algorithms, Optimizing in Graphs with Expensive Computation of Edge Weights, Fast and Deterministic Approximations for k-Cut., On the (co)girth of a connected matroid, Finding densest \(k\)-connected subgraphs, A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph, A new?old algorithm for minimum-cut and maximum-flow in closure graphs, Blocking unions of arborescences, Blocking optimal structures, A linear time algorithm for computing 3-edge-connected components in a multigraph, Two strongly polynomial cut cancelling algorithms for minimum cost network flow, A reactive GRASP with path relinking for capacitated clustering, Graph connectivity and its augmentation: Applications of MA orderings, Optimal cuts in graphs and statistical mechanics, A fast algorithm for cactus representations of minimum cuts, Greedy splitting algorithms for approximating multiway partition problems, Unnamed Item, Heuristics for the central tree problem, Finding the \(k\) most vital edges with respect to minimum spanning trees for fixed \(k\), Unnamed Item, Unnamed Item, A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation, Connectivity interdiction, Minimum Cuts of Simple Graphs in Almost Always Linear Time, Submodular function minimization, Computing vertex-disjoint paths in large graphs using MAOs, Unnamed Item, Implementing an efficient minimum capacity cut algorithm, Symmetric submodular system: contractions and Gomory-Hu tree, A new and improved algorithm for the 3-cut problem, A General Framework for Graph Sparsification, Finding minimum 3-way cuts in hypergraphs, Faster algorithms for shortest path and network flow based on graph decomposition, Minimizing symmetric submodular functions, Random sampling and greedy sparsification for matroid optimization problems, Polyhedral structure of submodular and posi-modular systems, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, A fully combinatorial algorithm for submodular function minimization., Unnamed Item, A clustering algorithm based on graph connectivity
