A Fast Algorithm to Calculate Powers of a Boolean Matrix for Diameter Computation of Random Graphs

DOI10.1007/978-3-540-77891-2_6zbMath1132.05327OpenAlexW1581597233MaRDI QIDQ5452153

Oksam Chae, M. Abdullah-Al-Wadud, M.D. Abdur Razzaque, Choong Seon Hong

Publication date: 25 March 2008

Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77891-2_6

zbMATH Keywords

Computational ComplexityRandom GraphsAdjacency MatrixBoolean MatrixGraph Diameter

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Matrix multiplication via arithmetic progressions
• Gaussian elimination is not optimal
• On the number of circuits in random graphs
• On the diameter of a class of random graphs
• Efficient drawing of RNA secondary structure
• The diameter of sparse random graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A Fast Algorithm to Calculate Powers of a Boolean Matrix for Diameter Computation of Random Graphs