R. Grappe

Circuit and bond polytopes on series-parallel graphs

  • S. Borne
  • Pierre Fouilhoux
  • R. Grappe
  • Mathieu Lacroix
  • Pierre Pesneau
    • Categories Polyhedra Tags , , ,

    In this paper, we describe the circuit polytope on series-parallel graphs. We first show the existence of a compact extended formulation. Though not being explicit, its construction process helps us to inductively provide the description in the original space. As a consequence, using the link between bonds and circuits in planar graphs, we also describe … Read more

    Which Nonnegative Matrices Are Slack Matrices?

  • João Gouveia
  • Volker Kaibel
  • R. Grappe
  • K. Pashkovich
  • Richard Z. Robinson
  • Rekha R. Thomas
    • Categories Linear Programming, Polyhedra Tags , , ,

    In this paper we characterize the slack matrices of cones and polytopes among all nonnegative matrices. This leads to an algorithm for deciding whether a given matrix is a slack matrix. The underlying decision problem is equivalent to the polyhedral verifi cation problem whose complexity is unknown. Citation April 2013 Article Download View Which Nonnegative Matrices … Read more