A POLYNOMIAL ALGORITHM FOR ENUMERATING ALL VERTICES OF A BASE POLYHEDRON

スポンサーリンク

概要

• 論文の詳細を見る

• In general, it is difficult to enumerate all vertices of a polytope in polynomial time. Here we present a polynomial algorithm which enumerates all vertices of a submodular base polyhedron in O(n^3|V|) time and in O(n^2) space, where V is the vertex set of a base polyhedron and n the dimension of the underlying Euclidean space. Our algorithm is also polynomial delay, and a generalization of several enumeration algorithms.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Zhan Ping

  Department Of Environmental Information Edogawa University

関連論文

• A POLYNOMIAL ALGORITHM FOR ENUMERATING ALL VERTICES OF A BASE POLYHEDRON

スポンサーリンク