Information Bounds Are Weak in the Shortest Distance Problem

DOI10.1145/322203.322206MaRDI QIDQ3930655zbMATH OpenOpenAlexWikidataFDO

Authors Andrew Chi-Chih Yao, F. Frances Yao, Ron 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

decision tree modelFarkas lemmalower boundmaximum flowpolyhedronrealizable patternsshortest path

Mathematics Subject Classification ID

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

Cited in

(14)

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

This page was built for publication: Information Bounds Are Weak in the Shortest Distance Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3930655)