Graph connectivity and its augmentation: Applications of MA orderings
type: Item
instance of: scholarly article
title: Graph connectivity and its augmentation: Applications of MA orderings
zbMATH Open document ID: 0995.05081
DOI: 10.1016/S0166-218X(01)00349-3
author: Hiroshi Nagamochi
author: Toshihide Ibaraki
published in: Discrete Applied Mathematics
publication date: 2002-09-17T00:00:00Z
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1801740
zbMATH Keywords: graphs
zbMATH Keywords: MA ordering
zbMATH Keywords: minimum cuts
zbMATH Keywords: edge-connectivity
zbMATH Keywords: graph augmentation
zbMATH Keywords: polynomial time algorithms
MaRDI profile type: Publication
cites work: Q3056948
cites work: Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
cites work: Edge-Connectivity Augmentation with Partition Constraints
cites work: Edge-Connectivity Augmentation Preserving Simplicity
cites work: Augmenting undirected connectivity in RNC and in randomized \(\tilde{O}(n^3)\) time
cites work: The minimum augmentation of any graph to aK-edge-connected graph
cites work: Q5501810
cites work: Successive edge-connectivity augmentation problems
cites work: Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
cites work: Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation
cites work: Q4371290
cites work: A note on mixed graphs and directed splitting off
cites work: Augmentation Problems
cites work: Q4250191
cites work: Augmenting Graphs to Meet Edge-Connectivity Requirements
cites work: On sparse subgraphs preserving connectivity properties
cites work: Minimal edge-coverings of pairs of sets
cites work: Directed vertex-connectivity augmentation
cites work: Fibonacci heaps and their uses in improved network optimization algorithms
cites work: ANOTHER SIMPLE PROOF OF THE VALIDITY OF NAGAMOCHI AND IBARAKI'S MIN-CUT ALGORITHM AND QUEYRANNE'S EXTENSION TO SYMMETRIC SUBMODULAR FUNCTION MINIMIZATION
cites work: Efficient splitting off algorithms for graphs
cites work: How to Make a Square Grid Framework with Cables Rigid
cites work: Optimal Mixed Graph Augmentation
cites work: A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
cites work: Computing Vertex Connectivity: New Bounds from Old Techniques
cites work: On Four-Connecting a Triconnected Graph
cites work: A unifying augmentation algorithm for two-edge connectivity and biconnectivity
cites work: Finding a Smallest Augmentation to Biconnect a Graph
cites work: Q5595961
cites work: Q2721988
cites work: Q4370202
cites work: Q4250193
cites work: Q4249524
cites work: Q4938784
cites work: Optimal augmentation of a 2-vertex-connected multigraph to an \(\ell\)-edge-connected and 3-vertex-connected multigraph
cites work: Multigraph augmentation under biconnectivity and general edge-connectivity requirements
cites work: Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
cites work: On the optimal vertex-connectivity augmentation
cites work: A note on the vertex-connectivity augmentation problem
cites work: Q4263718
cites work: Augmenting Outerplanar Graphs
cites work: Q4037427
cites work: Data Security Equals Graph Connectivity
cites work: Q4228454
cites work: Q4542522
cites work: An $\NC$ Algorithm for Minimum Cuts
cites work: An Õ(n2) algorithm for minimum cuts
cites work: A new approach to the minimum cut problem
cites work: Q3880849
cites work: A Reduction Method for Edge-Connectivity in Graphs
cites work: Konstruktion aller n-fach kantenzusammenhaengenden Digraphen
cites work: Q3140458
cites work: Q3840350
cites work: A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
cites work: Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
cites work: Deterministic \(\tilde O(nm)\) time edge-splitting in undirected graphs
cites work: A note on minimizing submodular functions
cites work: Q4249525
cites work: Augmenting Edge-Connectivity over the Entire Range inÕ(nm) Time
cites work: Polyhedral structure of submodular and posi-modular systems
cites work: Implementing an efficient minimum capacity cut algorithm

Graph connectivity and its augmentation: Applications of MA orderings (cites work)
cites work: A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs

Graph connectivity and its augmentation: Applications of MA orderings (cites work)
cites work: A fast algorithm for cactus representations of minimum cuts

Graph connectivity and its augmentation: Applications of MA orderings (cites work)
cites work: An efficient algorithm for the minimum capacity cut problem

Graph connectivity and its augmentation: Applications of MA orderings (cites work)
cites work: On the structure of all minimum cuts in a network and applications

Graph connectivity and its augmentation: Applications of MA orderings (cites work)
cites work: Minimum block containing a given graph

Graph connectivity and its augmentation: Applications of MA orderings (cites work)
cites work: Minimizing symmetric submodular functions

Graph connectivity and its augmentation: Applications of MA orderings (cites work)
cites work: Q4398376

Graph connectivity and its augmentation: Applications of MA orderings (cites work)
cites work: On minimizing symmetric set functions

Graph connectivity and its augmentation: Applications of MA orderings (cites work)
cites work: A simple min-cut algorithm

Graph connectivity and its augmentation: Applications of MA orderings (cites work)
cites work: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

Graph connectivity and its augmentation: Applications of MA orderings (cites work)
cites work: Edge-connectivity augmentation problems

Graph connectivity and its augmentation: Applications of MA orderings (cites work)
cites work: A minimum 3-connectivity augmentation of a graph

Graph connectivity and its augmentation: Applications of MA orderings (cites work)
cites work: Undirected vertex-connectivity structure and smallest four-vertex-connectivity augmentation (extended abstract)

Graph connectivity and its augmentation: Applications of MA orderings (full work available at URL)
full work available at URL: s0166-218x(01)00349-3

Graph connectivity and its augmentation: Applications of MA orderings (OpenAlex ID)
OpenAlex ID: W2071921460