Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing

DOI10.1007/3-540-58201-0_94MaRDI QIDQ4632452zbMATH OpenOpenAlexFDO

Authors Krishna Palem, Sotiris E. Nikoletseas, P. G. Spirakis, Moti Yung

Publication date 29 April 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-58201-0_94

zbMATH Keywords

disjoint pathfailure probabilitygiant componentrandom graphregular graph

Mathematics Subject Classification ID

Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80) Network design and communication in computer systems (68M10) Reliability, testing and fault tolerance of networks and computer systems (68M15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 871922
• On the robustness of interconnections in random graphs: a symbolic approach.
• Connectivity properties in random regular graphs with edge faults
• scientific article; zbMATH DE number 1003293
• scientific article; zbMATH DE number 3884207

Cites work

• Constructing disjoint paths on expander graphs
• Efficient dispersal of information for security, load balancing, and fault tolerance
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 3943863 (Why is no real title available?)
• Network Flow and Testing Graph Connectivity
• The birth of the giant component
• The Complexity of Enumeration and Reliability Problems

Cited in

(13)

• Expander properties and the cover time of random intersection graphs
• The parallel complexity of approximating the high degree subgraph problem
• Analysis of edge deletion processes on faulty random regular graphs.
• Interval routing in reliability networks
• On the robustness of interconnections in random graphs: a symbolic approach.
• The Second Eigenvalue of Random Walks On Symmetric Random Intersection Graphs
• scientific article; zbMATH DE number 1759469 (Why is no real title available?)
• Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time
• The giant component threshold for random regular graphs with edge faults H. Prodinger
• Random regular graphs with edge faults: Expansion through cores
• The parallel complexity of approximating the High Degree Subgraph problem
• Randomized parallel algorithms
• Large independent sets in general random intersection graphs

This page was built for publication: Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing

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