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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Yoshiko T. IKEBE, Akihisa TAMURA, "Polyhedral Proof of a Characterization of Perfect Bidirected Graphs" in IEICE TRANSACTIONS on Fundamentals,
vol. E86-A, no. 5, pp. 1000-1007, May 2003, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e86-a_5_1000/_p
Copy
@ARTICLE{e86-a_5_1000,
author={Yoshiko T. IKEBE, Akihisa TAMURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Polyhedral Proof of a Characterization of Perfect Bidirected Graphs},
year={2003},
volume={E86-A},
number={5},
pages={1000-1007},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Polyhedral Proof of a Characterization of Perfect Bidirected Graphs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1000
EP - 1007
AU - Yoshiko T. IKEBE
AU - Akihisa TAMURA
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E86-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2003
AB - 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.
ER -