Sparse reliable graph backbones

DOI10.1016/j.ic.2011.10.007zbMath1242.05144OpenAlexW2034942944MaRDI QIDQ418121

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

Related Items

Unnamed Item, Algorithms for enumerating multiple leaf-distance granular regular \(\alpha\)-subtree of unicyclic and edge-disjoint bicyclic graphs, On enumerating algorithms of novel multiple leaf-distance granular regular \(\alpha\)-subtrees of trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Inapproximability of the Tutte polynomial
• Random Sampling in Cut, Flow, and Network Design Problems
• Polynomial-Time Approximation Algorithms for the Ising Model
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Graph spanners
• The Complexity of Enumeration and Reliability Problems
• A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem
• On the computational complexity of the Jones and Tutte polynomials
• An Optimal Synchronizer for the Hypercube
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• Twice-ramanujan sparsifiers
• Reliable circuits using less reliable relays