Sparse reliable graph backbones

DOI10.1016/J.IC.2011.10.007zbMATH Open1242.05144OpenAlexW2034942944MaRDI QIDQ418121FDOQ418121

Authors Shiri Chechik, Yuval Emek, Boaz Patt-Shamir, David Peleg

Publication date 24 May 2012

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2011.10.007

zbMATH Keywords

network reliabilitysparse subgraphstutte polynomial

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Graph polynomials (05C31) Connectivity (05C40) Density (toughness, etc.) (05C42) Stochastic network models in operations research (90B15)

Recommendations

• Sparse reliable graph backbones
• On reliability of graphs with node failures
• Uniformly least reliable graphs in class \(\Omega (n,e)\) as \(e\leq n+1\).
• Network reliability
• scientific article; zbMATH DE number 3884207

Cites work

• scientific article; zbMATH DE number 67324 (Why is no real title available?)
• scientific article; zbMATH DE number 3523603 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 795224 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• An Optimal Synchronizer for the Hypercube
• Graph spanners
• Inapproximability of the Tutte polynomial
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• On the computational complexity of the Jones and Tutte polynomials
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• Polynomial-Time Approximation Algorithms for the Ising Model
• Random sampling in cut, flow, and network design problems
• Reliable circuits using less reliable relays
• The Complexity of Enumeration and Reliability Problems
• Twice-Ramanujan sparsifiers

Cited in

(4)

• Algorithms for enumerating multiple leaf-distance granular regular \(\alpha\)-subtree of unicyclic and edge-disjoint bicyclic graphs
• Sparse reliable graph backbones
• Computing exact minimum cuts without knowing the graph
• On enumerating algorithms of novel multiple leaf-distance granular regular \(\alpha\)-subtrees of trees

This page was built for publication: Sparse reliable graph backbones

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