Computing extremal and approximate distances in graphs having unit cost edges
From MaRDI portal
Publication:1145636
DOI10.1007/BF00264532zbMath0445.90090MaRDI QIDQ1145636
Richard J. Lipton, Kellogg S. Booth
Publication date: 1981
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00264532
undirected graphs; binary search; computation of distances; Strassen-like matrix multiplication algorithm; unit cost (unweighted) edges
90C35: Programming involving graphs or networks
65K05: Numerical mathematical programming methods
05C20: Directed graphs (digraphs), tournaments
Related Items
A new algorithm for finding a pseudoperipheral vertex or the endpoints of a pseudodiameter in a graph, On sparse matrix orderings in interior point methods, Finding pseudoperipheral nodes in graphs, Combinatorial analysis (nonnegative matrices, algorithmic problems)