Biconnectivity approximations and graph carvings
From MaRDI portal
Publication:4299007
DOI10.1145/174652.174654zbMath0822.68082OpenAlexW2092113566WikidataQ129991806 ScholiaQ129991806MaRDI QIDQ4299007
Publication date: 9 October 1995
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/174652.174654
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
An Improved Approximation Algorithm for the Matching Augmentation Problem ⋮ A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs ⋮ A \(\frac{5}{4}\)-approximation for subcubic 2EC using circulations and obliged edges ⋮ Approximating a class of combinatorial problems with rational objective function ⋮ Survivable network design: the capacitated minimum spanning network problem ⋮ A simple LP-based approximation algorithm for the matching augmentation problem ⋮ On finding two-connected subgraphs in planar graphs ⋮ Power optimization for connectivity problems ⋮ On the \(L_{\infty}\)-norm of extreme points for crossing supermodular directed network LPs ⋮ Fast Distributed Approximation for TAP and 2-Edge-Connectivity ⋮ Correlation clustering and two-edge-connected augmentation for planar graphs ⋮ Two-Connected Spanning Subgraphs with at Most $\frac{10}{7}{OPT}$ Edges ⋮ A new approximation algorithm for the minimum 2-edge-connected spanning subgraph problem ⋮ Approximation algorithms for flexible graph connectivity ⋮ Color-avoiding connected spanning subgraphs with minimum number of edges ⋮ Relay placement for fault tolerance in wireless networks in higher dimensions ⋮ Approximating Minimum Cost Connectivity Orientation and Augmentation ⋮ GMPLS label space minimization through hypergraph layouts ⋮ Finding 2-edge connected spanning subgraphs. ⋮ Approximating bounded-degree spanning trees and connected factors with leaves ⋮ Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs ⋮ A PTAS for Three-Edge-Connected Survivable Network Design in Planar Graphs ⋮ Approximation algorithms for connected graph factors of minimum weight ⋮ Fast distributed approximation for TAP and 2-edge-connectivity ⋮ On minimum power connectivity problems ⋮ On the hardness of constructing minimal 2-connected spanning subgraphs in complete graphs with sharpened triangle inequality ⋮ ON THE VERTEX-CONNECTIVITY PROBLEM FOR GRAPHS WITH SHARPENED TRIANGLE INEQUALITY ⋮ A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs ⋮ The generalized minimum edge-biconnected network problem: Efficient neighborhood structures for variable neighborhood search ⋮ Network flow spanners ⋮ Dual-based approximation algorithms for cut-based network connectivity problems ⋮ On the minimum-cost \(\lambda\)-edge-connected \(k\)-subgraph problem ⋮ Approximation algorithms for graph augmentation ⋮ On \(k\)-connectivity problems with sharpened triangle inequality ⋮ Fast exact algorithms for survivable network design with uniform requirements ⋮ Probabilistic properties of highly connected random geometric graphs ⋮ Modifying edges of a network to obtain short subgraphs ⋮ On the maximum size of a minimal \(k\)-edge connected augmentation ⋮ Algorithms for a network design problem with crossing supermodular demands ⋮ Designing Hypergraph Layouts to GMPLS Routing Strategies ⋮ An efficient approximation algorithm for the survivable network design problem ⋮ Vertex covering by paths on trees with its applications in machine translation ⋮ Approximation algorithms for vertex-connectivity augmentation on the cycle ⋮ Relay placement for two-connectivity ⋮ Approximating unweighted connectivity problems in parallel ⋮ Strongly Connected Spanning Subgraph for Almost Symmetric Networks ⋮ Approximating minimum size \{1,2\}-connected networks ⋮ An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
This page was built for publication: Biconnectivity approximations and graph carvings
