A first efficient algorithm for enumerating all the extreme points of a bisubmodular polyhedron
<|reference_start|>A first efficient algorithm for enumerating all the extreme points of a bisubmodular polyhedron: Efficiently enumerating all the extreme points of a polytope identified by a system of linear inequalities is a well-known challenge issue.We consider a special case and present an algorithm that enumerates all the extreme points of a bisubmodular polyhedron in $\mathcal{O}(n^4|V|)$ time and $\mathcal{O}(n^2)$ space complexity, where $ n$ is the dimension of underlying space and $V$ is the set of outputs. We use the reverse search and signed poset linked to extreme points to avoid the redundant search. Our algorithm is a generalization of enumerating all the extreme points of a base polyhedron which comprises some combinatorial enumeration problems.<|reference_end|>
@article{matsui2024a,
    title={A first efficient algorithm for enumerating all the extreme points of a
  bisubmodular polyhedron},
    author={Yasuko Matsui, Takeshi Naitoh, Ping Zhan},
    journal={arXiv preprint arXiv:2405.01039},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.01039},
    primaryClass={cs.DM}
}