Computing extremal and approximate distances in graphs having unit cost edges

DOI10.1007/BF00264532zbMath0445.90090OpenAlexW2019730496MaRDI 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

zbMATH Keywords

undirected graphsbinary searchcomputation of distancesStrassen-like matrix multiplication algorithmunit cost (unweighted) edges

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Numerical mathematical programming methods (65K05) Directed graphs (digraphs), tournaments (05C20)

Related Items (4)

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)

This page was built for publication: Computing extremal and approximate distances in graphs having unit cost edges