Information Bounds Are Weak in the Shortest Distance Problem

DOI10.1145/322203.322206zbMath0475.68043OpenAlexW2105310556WikidataQ106189869 ScholiaQ106189869MaRDI QIDQ3930655

Andrew Chi-Chih Yao, F. Frances Yao, Ronald L. Graham

Publication date: 1980

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322203.322206

zbMATH Keywords

shortest pathpolyhedronlower boundmaximum flowFarkas lemmadecision tree modelrealizable patterns

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)

Related Items

Legal coloring of graphs, A new approach to all-pairs shortest paths on real-weighted graphs, Graphic vertices of the metric polytope, The structure of distances in networks, On the number of upward planar orientations of maximal planar graphs, Acyclic orientations of random graphs, Elements of a theory of simulation. II: Sequential dynamical systems., Monomial bases for broken circuit complexes, Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph, A classification of the six-point prime metrics, The coherency index, Unnamed Item, Linear verification for spanning trees, Every poset has a central element