Generating Sparse 2-Spanners
From MaRDI portal
Publication:4312222
DOI10.1006/jagm.1994.1032zbMath1427.68246OpenAlexW2057046770MaRDI QIDQ4312222
Publication date: 22 November 1995
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jagm.1994.1032
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Connectivity (05C40)
Related Items
Sparse hop spanners for unit disk graphs ⋮ A fast network-decomposition algorithm and its applications to constant-time distributed computation ⋮ Models and algorithms for network reduction ⋮ A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation ⋮ Minimum \(t\)-spanners on subcubic graphs ⋮ Covering a graph with densest subgraphs ⋮ A study on modularity density maximization: column generation acceleration and computational complexity analysis ⋮ Approximation of minimum weight spanners for sparse graphs ⋮ Unnamed Item ⋮ Spanners in sparse graphs ⋮ Improved Approximation for the Directed Spanner Problem ⋮ Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences ⋮ Edge-disjoint spanners in Cartesian products of graphs ⋮ Randomized priority algorithms ⋮ Approximating \(k\)-spanner problems for \(k>2\) ⋮ A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs ⋮ Graph spanners: a tutorial review ⋮ Edge-disjoint spanners in tori ⋮ Distance-Preserving Graph Contractions ⋮ Sparse hypercube 3-spanners ⋮ On the approximability and hardness of the minimum connected dominating set with routing cost constraint ⋮ Distributed Spanner Approximation ⋮ Edge-disjoint spanners of complete graphs and complete digraphs ⋮ Computing the \(k\) densest subgraphs of a graph ⋮ NP-completeness of minimum spanner problems
