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

DOI10.1007/3-540-58201-0_94zbMath1422.68192OpenAlexW1592720058MaRDI QIDQ4632452

Krishna V. Palem, Sotiris E. Nikoletseas, Mordechai M. Yung, Paul G. Spirakis

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

regular graphrandom graphfailure probabilitydisjoint pathgiant component

Mathematics Subject Classification ID

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

Related Items (9)

Analysis of edge deletion processes on faulty random regular graphs. ⋮ The Second Eigenvalue of Random Walks On Symmetric Random Intersection Graphs ⋮ Stochastic graphs have short memory: Fully dynamic connectivity in poly-log expected time ⋮ Large independent sets in general random intersection graphs ⋮ Interval routing in reliability networks ⋮ 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 ⋮ Expander properties and the cover time of random intersection graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast probabilistic algorithms for Hamiltonian circuits and matchings
• Constructing disjoint paths on expander graphs
• Efficient dispersal of information for security, load balancing, and fault tolerance
• The Complexity of Enumeration and Reliability Problems
• Network Flow and Testing Graph Connectivity
• The birth of the giant component

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