Graph connectivity and its augmentation: Applications of MA orderings
From MaRDI portal
Publication:697579
DOI10.1016/S0166-218X(01)00349-3zbMath0995.05081MaRDI QIDQ697579
Toshihide Ibaraki, Hiroshi Nagamochi
Publication date: 17 September 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
graphs; edge-connectivity; graph augmentation; polynomial time algorithms; minimum cuts; MA ordering
Related Items
Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs, Sparse connectivity certificates via MA orderings in graphs, Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs, On the minimum local-vertex-connectivity augmentation in graphs, A maximum flow algorithm using MA ordering., Sparse certificates and removable cycles in \(l\)-mixed \(p\)-connected graphs, Augmenting forests to meet odd diameter requirements, Minimum Cuts of Simple Graphs in Almost Always Linear Time
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on minimizing submodular functions
- An efficient algorithm for the minimum capacity cut problem
- Edge-connectivity augmentation problems
- Konstruktion aller n-fach kantenzusammenhaengenden Digraphen
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A minimum 3-connectivity augmentation of a graph
- Minimum block containing a given graph
- A unifying augmentation algorithm for two-edge connectivity and biconnectivity
- Minimizing symmetric submodular functions
- Directed vertex-connectivity augmentation
- Successive edge-connectivity augmentation problems
- Deterministic \(\tilde O(nm)\) time edge-splitting in undirected graphs
- A note on the vertex-connectivity augmentation problem
- Implementing an efficient minimum capacity cut algorithm
- Polyhedral structure of submodular and posi-modular systems
- On the optimal vertex-connectivity augmentation
- Minimal edge-coverings of pairs of sets
- A simplified \(\widetilde{O}(nm)\) time edge-splitting algorithm in undirected graphs
- Optimal augmentation of a 2-vertex-connected multigraph to an \(\ell\)-edge-connected and 3-vertex-connected multigraph
- A fast algorithm for cactus representations of minimum cuts
- Multigraph augmentation under biconnectivity and general edge-connectivity requirements
- Augmenting undirected connectivity in RNC and in randomized Õ(n3) time
- Efficient splitting off algorithms for graphs
- Finding a Smallest Augmentation to Biconnect a Graph
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Optimal Mixed Graph Augmentation
- Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
- The minimum augmentation of any graph to aK-edge-connected graph
- On the structure of all minimum cuts in a network and applications
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
- Augmentation Problems
- A Reduction Method for Edge-Connectivity in Graphs
- On sparse subgraphs preserving connectivity properties
- Edge-Connectivity Augmentation Preserving Simplicity
- Augmenting Edge-Connectivity over the Entire Range inÕ(nm) Time
- Edge-Connectivity Augmentation with Partition Constraints
- A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
- An $\NC$ Algorithm for Minimum Cuts
- A new approach to the minimum cut problem
- A simple min-cut algorithm
- On Four-Connecting a Triconnected Graph
- How to Make a Square Grid Framework with Cables Rigid
- ANOTHER SIMPLE PROOF OF THE VALIDITY OF NAGAMOCHI AND IBARAKI'S MIN-CUT ALGORITHM AND QUEYRANNE'S EXTENSION TO SYMMETRIC SUBMODULAR FUNCTION MINIMIZATION
- Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
- Data Security Equals Graph Connectivity
- Augmenting Outerplanar Graphs
- Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation
- Computing Vertex Connectivity: New Bounds from Old Techniques
- Fibonacci heaps and their uses in improved network optimization algorithms
- An Õ(n2) algorithm for minimum cuts
- On minimizing symmetric set functions
