2007 | OriginalPaper | Buchkapitel
Finding a Polytope from Its Graph in Polynomial Time
verfasst von : Eric J. Friedman
Erschienen in: Integer Programming and Combinatorial Optimization
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We show that one can compute a (simple) polytope from its graph in Polynomial time. This computation of a polytope from its graph was shown to be solvable by Blind and Mani and more recently Kalai provided a simple proof that leads to an exponential time algorithm. Our proof relies on a Primal-Dual characterization by Joswig, Kaibel and Korner. We describe an exponential Linear Programming which can be used to construct the solution and show that it can be solved in polynomial time.