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

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

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)

Cites Work

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

Cited In (4)

• On enumerating algorithms of novel multiple leaf-distance granular regular \(\alpha\)-subtrees of trees
• Sparse reliable graph backbones
• Algorithms for enumerating multiple leaf-distance granular regular \(\alpha\)-subtree of unicyclic and edge-disjoint bicyclic graphs
• Title not available (Why is that?)

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)