首页    期刊浏览 2024年12月11日 星期三
登录注册

文章基本信息

  • 标题:Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices
  • 作者:Khaled Elbassioni ; Kazuhisa Makino
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:101
  • 页码:18:1-18:14
  • DOI:10.4230/LIPIcs.SWAT.2018.18
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron P=P(A,1_)={x in R^n | Ax >= 1_, x >= 0_}, when A is a totally unimodular matrix. Our algorithm is based on decomposing the hypergraph transversal problem for unimodular hypergraphs using Seymour's decomposition of totally unimodular matrices, and may be of independent interest.
  • 关键词:Totally unimodular matrices; Vertices of polyhedra; Vertex enumeration; Hypergraph transversals; Hypergraph decomposition; Output polynomial-time algo
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有