Graph connectivity and its augmentation: Applications of MA orderings
From MaRDI portal
Publication:697579
DOI10.1016/S0166-218X(01)00349-3zbMATH Open0995.05081OpenAlexW2071921460MaRDI QIDQ697579FDOQ697579
Authors: Hiroshi Nagamochi, Toshihide Ibaraki 
Publication date: 17 September 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00349-3
Recommendations
- GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(<Special Issue>Network Design, Control and Optimization)
- scientific article; zbMATH DE number 1670666
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- NEW MAXIMUM FLOW ALGORITHMS BY MA ORDERMGS AND SCALING
- Sparse connectivity certificates via MA orderings in graphs
Cites Work
- Network flows. Theory, algorithms, and applications.
- Fibonacci heaps and their uses in improved network optimization algorithms
- A Reduction Method for Edge-Connectivity in Graphs
- Minimizing symmetric submodular functions
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A note on minimizing submodular functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Augmenting Graphs to Meet Edge-Connectivity Requirements
- On sparse subgraphs preserving connectivity properties
- Title not available (Why is that?)
- A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
- A new approach to the minimum cut problem
- Efficient splitting off algorithms for graphs
- Finding a Smallest Augmentation to Biconnect a Graph
- Augmentation Problems
- An efficient algorithm for the minimum capacity cut problem
- A simple min-cut algorithm
- On the structure of all minimum cuts in a network and applications
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- On the optimal vertex-connectivity augmentation
- Minimal edge-coverings of pairs of sets
- Title not available (Why is that?)
- Directed vertex-connectivity augmentation
- A note on the vertex-connectivity augmentation problem
- Title not available (Why is that?)
- Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
- On Four-Connecting a Triconnected Graph
- Title not available (Why is that?)
- Title not available (Why is that?)
- Undirected vertex-connectivity structure and smallest four-vertex-connectivity augmentation (extended abstract)
- Konstruktion aller n-fach kantenzusammenhaengenden Digraphen
- Edge-Connectivity Augmentation with Partition Constraints
- Edge-connectivity augmentation problems
- Title not available (Why is that?)
- Preserving and Increasing Local Edge-Connectivity in Mixed Graphs
- Computing Vertex Connectivity: New Bounds from Old Techniques
- Augmenting Outerplanar Graphs
- Minimum block containing a given graph
- Successive edge-connectivity augmentation problems
- Title not available (Why is that?)
- Augmenting Edge-Connectivity over the Entire Range inÕ(nm) Time
- Title not available (Why is that?)
- A minimum 3-connectivity augmentation of a graph
- A unifying augmentation algorithm for two-edge connectivity and biconnectivity
- Deterministic \(\tilde O(nm)\) time edge-splitting in undirected graphs
- Implementing an efficient minimum capacity cut algorithm
- Polyhedral structure of submodular and posi-modular systems
- 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 \(\tilde{O}(n^3)\) time
- Optimal Mixed Graph Augmentation
- The minimum augmentation of any graph to aK-edge-connected graph
- Title not available (Why is that?)
- Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
- Edge-Connectivity Augmentation Preserving Simplicity
- Title not available (Why is that?)
- A note on mixed graphs and directed splitting off
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- An $\NC$ Algorithm for Minimum Cuts
- Title not available (Why is that?)
- 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
- Data Security Equals Graph Connectivity
- Title not available (Why is that?)
- Fast Algorithms for k-Shredders and k-Node Connectivity Augmentation
- An Õ(n2) algorithm for minimum cuts
- On minimizing symmetric set functions
Cited In (15)
- The \((2, k)\)-connectivity augmentation problem: algorithmic aspects
- Minimum Cuts of Simple Graphs in Almost Always Linear Time
- Sparse connectivity certificates via MA orderings in graphs
- Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
- Augmenting edge-connectivity between vertex subsets
- GRAPH ALGORITHMS FOR NETWORK CONNECTIVITY PROBLEMS(<Special Issue>Network Design, Control and Optimization)
- A maximum flow algorithm using MA ordering.
- Minimum augmentation of local edge-connectivity between vertices and vertex subsets in undirected graphs
- Regular augmentation of planar graphs
- Sparse certificates and removable cycles in \(l\)-mixed \(p\)-connected graphs
- Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs
- Augmenting forests to meet odd diameter requirements
- Augmenting the edge connectivity of planar straight line graphs to three
- Connectivity augmentation in planar straight line graphs
- On the minimum local-vertex-connectivity augmentation in graphs
This page was built for publication: Graph connectivity and its augmentation: Applications of MA orderings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q697579)
