A Fast Algorithm to Calculate Powers of a Boolean Matrix for Diameter Computation of Random Graphs
From MaRDI portal
Publication:5452153
DOI10.1007/978-3-540-77891-2_6zbMath1132.05327MaRDI QIDQ5452153
Choong Seon Hong, Oksam Chae, M. Abdullah-Al-Wadud, M.D. Abdur Razzaque
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
68Q25: Analysis of algorithms and problem complexity
05C80: Random graphs (graph-theoretic aspects)
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
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