On the average length of lexicographic paths

DOI10.1007/BF01580885zbMATH Open0599.90076OpenAlexW2087817570MaRDI QIDQ3735459FDOQ3735459

Authors: A.-E. Nobs, Thomas M. Liebling, Michel Balinski 

Publication date: 1986

Published in: Mathematical Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01580885

Recommendations

• On the average path length of complete \(m\)-ary trees
• scientific article; zbMATH DE number 3858431
• On the average path length of a cycle plus random edges
• scientific article; zbMATH DE number 1535253
• On the average internal path length of m-ary search trees
• Average hopcount of the shortest path in tree-like components with finite size
• scientific article; zbMATH DE number 3876620
• On paths with the shortest average arc length in weighted graphs
• On the asymptotic average length of a maximum common subsequence for words over a finite alphabet
• On the path length of binary trees

zbMATH Keywords

complexitypolynomial algorithmdegeneraciesaverage lengthlexicographic pathrandomized simplex method

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• A note on degeneracy in linear programming
• On the length of simplex paths: The assignment case

Cited In (5)

• Post-optimality analysis of the optimal solution of a degenerate linear program using a pivoting algorithm
• A note on degeneracy in linear programming
• Degeneracy graphs: Theory and applications. An updated survey
• Selected bibliography on degeneracy
• A new pivoting rule for solving various degeneracy problems

This page was built for publication: On the average length of lexicographic paths

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