Efficient enumeration of the vertices of polyhedra associated with network LP's

1. A.V. Aho, J.E. Hopcroft and J.D. Ullman,The Design and Analysis of Computer Algorithms (Addison-Wesley, New York, 1974).

   Google Scholar 

2. W. Altherr, “An algorithm for enumerating all vertices of a convex polyhedron,”Computing 15 (1975) 181–193.

   Google Scholar 

3. D. Avis and K. Fukuda, “A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra,” Tech. Rept. SOCS-91.6, McGill University (Montréal, Qué., 1991).

   Google Scholar 

4. M.L. Balinski, “An algorithm for finding all vertices of convex polyhedral sets,”SIAM Journal on Applied Mathematics 9 (1961) 72–88.

   Google Scholar 

5. B. Chazelle, “An optimal convex hull algorithm and new results on cuttings (extended abstract),”Proceedings of 32nd IEEE FCOS (1991) 29–38.

6. M.S. Bazaraa and J.J. Jarvis,Linear Programming and Network Flows (Wiley, New York, 1977).

   Google Scholar 

7. M.E. Dyer, “The complexity of vertex enumeration methods,”Mathematics of Operations Research 8 (1983) 381–402.

   Google Scholar 

8. M.E. Dyer and L.G. Proll, “An algorithm for determining all extreme points of a convex polytope,”Mathematical Programming 12 (1977) 81–96.

   Google Scholar 

9. A.J. Goldman, “Resolution and separation theorems for polyhedral convex sets,” in: H.W. Kuhn and A.W. Tucker, eds.,Linear Inequalities and Related Systems (Princeton University Press, Princeton, NJ, 1956) pp. 53–97.

   Google Scholar 

10. E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, San Francisco, CA, 1976).

    Google Scholar 

11. M. Manas and J. Nedoma, “Finding all vertices of a convex polyhedron,”Numerische Mathematik 12 (1968) 226–229.

    Google Scholar 

12. T.H. Matthiess, “An algorithm for determining irrelevant constraints and all vertices in systems of linear inequalities,”Operations Research 21 (1973) 247–260.

    Google Scholar 

13. T.H. Matthiess and D.S. Rubin, “A survey and comparison of methods for finding all vertices of convex polyhedral sets,”Mathematics of Operations Research (1980) 167–185.

14. T.S. Motzkin, H. Raiffa, G.L. Thompson and R.M. Thrall, “The double description method,” in: H.W. Kuhn and A.W. Tucker, eds.,Contributions to the Theory of Games, Vol. 2 (Princeton University Press, Princeton, NJ, 1953) pp. 51–73.

    Google Scholar 

15. K.G. Murty,Linear Programming (Wiley, New York, 1983).

    Google Scholar 

16. J.S. Provan, “Efficient recognition of matroid and 2-monotonic systems,” in: R.D. Ringeisen and F.S. Roberts, eds.,Applications of Discrete Mathematics (SIAM, Philadelphia, PA, 1988) pp. 122–134.

    Google Scholar 

17. J.S. Provan and D.R. Shier, “A paradigm for listing (s, t)-cuts in graphs,” Tech. Rept. UNC/OR/TR91-3, University of North Carolina (Chapel Hill, NC, 1991).

    Google Scholar 

18. R.C. Read and R.E. Tarjan, “Bounds on backtrack algorithms for listing cycles, paths and spanning trees,”Networks 5 (1975) 237–252.

    Google Scholar 

19. D.S. Rubin, “Vertex generation and cardinality constrained linear programs,”Operations Research 23 (1975) 555–564.

    Google Scholar 

20. D.S. Rubin, “Vertex generation methods for problems with logical constraints,”Annals of Discrete Mathematics 1 (1977) 457–466.

    Google Scholar 

21. R. Seidel, “Constructing higher-dimensional convex hulls at logarithmic cost per face,”Proceedings of the 18th ACM STOC (1986) 404–413.

22. G. Swart, “Finding the convex hull facet by facet,”Journal of Algebra 6 (1985) 17–48.

    Google Scholar 

Download references