The search functionality is under construction.
The search functionality is under construction.

Keyword Search Result

[Keyword] 0-1 polytopes(1hit)

1-1hit
  • Polyhedral Proof of a Characterization of Perfect Bidirected Graphs

    Yoshiko T. IKEBE  Akihisa TAMURA  

     
    PAPER

      Vol:
    E86-A No:5
      Page(s):
    1000-1007

    Bidirected graphs which are generalizations of undirected graphs, have three types of edges: (+,+)-edges, (-,-)-edges and (+,-)-edges. Undirected graphs are regarded as bidirected graphs whose edges are all of type (+,+). The notion of perfection of undirected graphs can be naturally extended to bidirected graphs in terms of polytopes. The fact that a bidirected graph is perfect if and only if the undirected graph obtained by replacing all edges to (+,+) is perfect was independently proved by several researchers. This paper gives a polyhedral proof of the fact and introduces some new knowledge on perfect bidirected graphs.