scientific article; zbMATH DE number 7651209

DOI10.4230/LIPICS.ESA.2020.70MaRDI QIDQ5874542zbMATH OpenFDO

Authors Bogdan-Adrian Manghiuc, Pan Peng, He Sun

Publication date 7 February 2023

Full work available at URL https://arxiv.org/abs/2006.14449

zbMATH Keywords

algebraic connectivitygraph sparsificationsemidefinite programming

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A combinatorial, primal-dual approach to semidefinite programs
• An \(O(\log^2{k})\)-approximation algorithm for the \(k\)-vertex connected spanning subgraph problem
• An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
• An SDP-based algorithm for linear-sized spectral sparsification
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Approximating low-stretch spanners
• Approximating minimum-cost \(k\)-node connected subgraphs via independence-free graphs
• Constructing linear-sized spectral sparsification in almost-linear time
• Design networks with bounded pairwise distance
• Expander codes
• Fastest Mixing Markov Chain on a Graph
• Graph-theoretic properties in computational complexity
• Hardness of Approximation for Vertex-Connectivity Network Design Problems
• scientific article; zbMATH DE number 5485528 (Why is no real title available?)
• scientific article; zbMATH DE number 3417498 (Why is no real title available?)
• Maximum algebraic connectivity augmentation is NP-hard
• Minimizing Effective Resistance of a Graph
• On expander codes
• Optimal Approximate Matrix Product in Terms of Stable Rank
• Parameters of two-prover-one-round game and the hardness of connectivity problems
• Partitioning into expanders
• Partitioning well-clustered graphs: spectral clustering works!
• Proportional volume sampling and approximation algorithms for \(A\)-optimal design
• Pseudorandomness for network algorithms
• QIP = PSPACE
• Single pass spectral sparsification in dynamic streams
• Spectral sparsification and regret minimization beyond matrix multiplicative updates
• Spectral sparsification in the semi-streaming setting
• Spectral sparsification of graphs
• Subgraph sparsification and nearly optimal ultrasparsifiers
• Towards an SDP-based approach to spectral methods: a nearly-linear-time algorithm for graph partitioning and decomposition
• Twice-Ramanujan sparsifiers

Cited in

(3)

• Augmenting chains in graphs without a skew star.
• On algebraic connectivity augmentation
• On finding augmenting graphs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874542)