Edge-connectivity augmentation problems
From MaRDI portal
Publication:1091147
DOI10.1016/0022-0000(87)90038-9zbMath0622.68057OpenAlexW2067818080MaRDI QIDQ1091147
Publication date: 1987
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(87)90038-9
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Connectivity (05C40)
Related Items (59)
Augmenting weighted graphs to establish directed point-to-point connectivity ⋮ BOUNDED LENGTH, 2-EDGE AUGMENTATION OF GEOMETRIC PLANAR GRAPHS ⋮ On triconnected and cubic plane graphs on given point sets ⋮ Minimum cost subpartitions in graphs ⋮ Connectivity augmentation in plane straight line graphs ⋮ Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs ⋮ Minimum degree orderings ⋮ Augmenting the connectivity of outerplanar graphs ⋮ Structured Connectivity Augmentation ⋮ Triangulating planar graphs while minimizing the maximum degree ⋮ An application of submodular flows ⋮ Covering symmetric supermodular functions by uniform hypergraphs ⋮ Covering symmetric supermodular functions with graph edges: a short proof of a theorem of Benczúr and Frank ⋮ Structured Connectivity Augmentation ⋮ The Generalized Terminal Backup Problem ⋮ A faster edge splitting algorithm in multigraphs and its application to the edge-connectivity augmentation problem ⋮ How to make a strongly connected digraph two-connected ⋮ A New Approach to Splitting-Off ⋮ Provision of maximum connectivity resiliency with minimum cost to telecommunication networks through third‐party networks ⋮ Augmenting the rigidity of a graph in \(\mathbb R^{2}\) ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ Pushdown-reduce: An algorithm for connectivity augmentation and poset covering problems ⋮ Network augmentation for disaster‐resilience against geographically correlated failure ⋮ Combined connectivity augmentation and orientation problems ⋮ Partition Constrained Covering of a Symmetric Crossing Supermodular Function by a Graph ⋮ Approximating Minimum Cost Connectivity Orientation and Augmentation ⋮ Edge-Connectivity Augmentations of Graphs and Hypergraphs ⋮ Path-contractions, edge deletions and connectivity preservation ⋮ Augmenting the edge connectivity of planar straight line graphs to three ⋮ Testing Eulerianity and connectivity in directed sparse graphs ⋮ Augmenting edge-connectivity between vertex subsets ⋮ Augmenting the connectivity of geometric graphs ⋮ Multigraph augmentation under biconnectivity and general edge-connectivity requirements ⋮ Tight approximation algorithm for connectivity augmentation problems ⋮ Connectivity augmentation in planar straight line graphs ⋮ On the cycle augmentation problem: hardness and approximation algorithms ⋮ Minimizing a monotone concave function with laminar covering constraints ⋮ Augmenting the Edge‐Connectivity of a Hypergraph by Adding a Multipartite Graph ⋮ A minimum 3-connectivity augmentation of a graph ⋮ Graph connectivity and its augmentation: Applications of MA orderings ⋮ Local edge-connectivity augmentation in hypergraphs is NP-complete ⋮ Independence free graphs and vertex connectivity augmentation ⋮ An algorithm for source location in directed graphs ⋮ A computational investigation of heuristic algorithms for 2-edge-connectivity augmentation ⋮ Connectivity interdiction ⋮ Augmenting forests to meet odd diameter requirements ⋮ Augmenting trees so that every three vertices lie on a cycle ⋮ Edge-connectivity augmentation of graphs over symmetric parity families ⋮ Approximation algorithms for graph augmentation ⋮ The \((2, k)\)-connectivity augmentation problem: algorithmic aspects ⋮ Posimodular function optimization ⋮ Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs ⋮ Making bidirected graphs strongly connected ⋮ Regular augmentation of planar graphs ⋮ A smallest augmentation to 3-connect a graph ⋮ A UNIFIED FRAMEWORK FOR BI(TRI)CONNECTIVITY AND CHORDAL AUGMENTATION ⋮ Path-Contractions, Edge Deletions and Connectivity Preservation ⋮ Augmenting the edge-connectivity of a hypergraph by adding a multipartite graph ⋮ Augmenting a tree to a \(k\)-arbor-connected graph with pagenumber \(k\)
Cites Work
- Parallel concepts in graph theory
- Approximation Algorithms for Several Graph Augmentation Problems
- Augmentation Problems
- Smallest Augmentations to Biconnect a Graph
- `` Strong NP-Completeness Results
- A Reduction Method for Edge-Connectivity in Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Edge-connectivity augmentation problems
