Linear Program Optimal Extreme Points

[Prabhu Manyem]

To Andrew, Peter and Manuel,

Thank you for your help on this topic.

To Manuel, Why only vertices next to the starting vertex?  If the
links are A-->B-->C and B-->D, so first you go from A to B, then B to
C, then backtrack to B (from C), and then you can go from B to D...
This is what I had in mind when I said "traverse in a tree-like
fashion".. (But yes, to do backtracking, you should store the Bases of
A and B in memory).

But in the example that you gave, I can walk directly from BR (bottom
right) to TR (top right), or from TL to TR.

To Peter-- Yes, they can have exponentially many vertices.. But I
think there are "doubly polynomial" algorithms that can do
enumeration.. Doubly Polynomial means, polynomial in the size of the
input+output.. Here is one reference:
https://www.research-collection.ethz.ch/handle/20.500.11850/426218
(Chapter 8, I think).. I came to know about this only recently.

Best,
-Prabhu