scientific article; zbMATH DE number 1334210

DOI10.1002/(SICI)1097-0037(199907)33:4%3C249::AID-NET2%3E3.0.CO;2-7MaRDI QIDQ4262014zbMATH OpenFDO

Authors Nicholas Pippenger

Publication date 27 November 2000

Full work available at URL https://doi.org/10.1002/(SICI)1097-0037(199907)33:4%3C249::AID-NET2%3E3.0.CO;2-7

zbMATH Keywords

channel graphcutfailure probabilityinterconnection networklinking probabilityparallel graphpathspider-web graphvacancy probability

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial probability (60C05) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Search theory (90B40) Abstract computational complexity for mathematical programming problems (90C60) Analytic circuit theory (94C05) Applications of graph theory to circuits and networks (94C15)

Recommendations

• scientific article; zbMATH DE number 1535253
• Local versus global search in channel graphs
• scientific article; zbMATH DE number 3982535
• A bidirectional shortest-path algorithm with good average-case behavior
• scientific article; zbMATH DE number 934538

Cites work

• On Crossbar Switching Networks
• Optimal Rearrangeable Multistage Connecting Networks
• Proving the Rearrangeability of Connecting Networks by Group Calculations
• Rearrangeable Networks with Limited Depth
• Routing algorithms for switching networks with probabilistic traffic
• The asymptotic optimality of spider-web networks
• The blocking probability of spider-web networks
• The Connection Patterns of Two Complete Binary Trees

Cited in

(6)

• The average complexity of depth-first search with backtracking and cutoff
• Average-Case Lower Bounds for Searching
• scientific article; zbMATH DE number 1535253 (Why is no real title available?)
• Local versus global search in channel graphs
• The Linking Probability of Deep Spider-Web Networks
• Average-case analysis of best-first search in two representative directed acyclic graphs

This page was built for publication:

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