Geodesic
Transitive closure and transitive reduction in bidirected graphs
Czechoslovak Mathematical Journal, Tome 69 (2019) no. 2, pp. 295-315
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

In a bidirected graph, an edge has a direction at each end, so bidirected graphs generalize directed graphs. We generalize the definitions of transitive closure and transitive reduction from directed graphs to bidirected graphs by introducing new notions of bipath and bicircuit that generalize directed paths and cycles. We show how transitive reduction is related to transitive closure and to the matroids of the signed graph corresponding to the bidirected graph.
In a bidirected graph, an edge has a direction at each end, so bidirected graphs generalize directed graphs. We generalize the definitions of transitive closure and transitive reduction from directed graphs to bidirected graphs by introducing new notions of bipath and bicircuit that generalize directed paths and cycles. We show how transitive reduction is related to transitive closure and to the matroids of the signed graph corresponding to the bidirected graph.
DOI : 10.21136/CMJ.2019.0644-16
Classification : 05C20, 05C22, 05C38
Keywords: bidirected graph; signed graph; matroid; transitive closure; transitive reduction 
@article{10_21136_CMJ_2019_0644_16,
     author = {Bessouf, Ouahiba and Khelladi, Abdelkader and Zaslavsky, Thomas},
     title = {Transitive closure and transitive reduction in bidirected graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {295--315},
     year = {2019},
     volume = {69},
     number = {2},
     doi = {10.21136/CMJ.2019.0644-16},
     mrnumber = {3959945},
     zbl = {07088785},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0644-16/}
}
TY  - JOUR
AU  - Bessouf, Ouahiba
AU  - Khelladi, Abdelkader
AU  - Zaslavsky, Thomas
TI  - Transitive closure and transitive reduction in bidirected graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2019
SP  - 295
EP  - 315
VL  - 69
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0644-16/
DO  - 10.21136/CMJ.2019.0644-16
LA  - en
ID  - 10_21136_CMJ_2019_0644_16
ER  - 
%0 Journal Article
%A Bessouf, Ouahiba
%A Khelladi, Abdelkader
%A Zaslavsky, Thomas
%T Transitive closure and transitive reduction in bidirected graphs
%J Czechoslovak Mathematical Journal
%D 2019
%P 295-315
%V 69
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2019.0644-16/
%R 10.21136/CMJ.2019.0644-16
%G en
%F 10_21136_CMJ_2019_0644_16
Bessouf, Ouahiba; Khelladi, Abdelkader; Zaslavsky, Thomas. Transitive closure and transitive reduction in bidirected graphs. Czechoslovak Mathematical Journal, Tome 69 (2019) no. 2, pp. 295-315. doi: 10.21136/CMJ.2019.0644-16

[1] Aho, A. V., Garey, M. R., Ullman, J. D.: The transitive reduction of a directed graph. SIAM J. Comput. 1 (1972), 131-137. | DOI | MR | JFM

[2] Berge, C.: Théorie des graphes et ses applications. Collection Universitaire de Mathématiques, 2, Dunod, Paris French (1958). | MR | JFM

[3] Bessouf, O.: Menger's Theorem in the Bidirected Graphs. Master's Thesis, Faculty of Mathematics, University of Science and Technology Houari Boumediene, Algiers French (1999).

[4] Harary, F.: On the notion of balance of a signed graph. Mich. Math. J. 2 (1954), 143-146. | DOI | MR | JFM

[5] Harary, F.: Structural duality. Behavioral Sci. 2 (1957), 255-265. | DOI | MR

[6] Khelladi, A.: Algebraic Properties of Combinative Structures. Thesis of Doctorate of State, Institute of Mathematics, University of Science and Technology Houari Boumediene, Algiers French (1985).

[7] Khelladi, A.: Nowhere-zero integral chains and flows in bidirected graphs. J. Comb. Theory, Ser. B 43 (1987), 95-115. | DOI | MR | JFM

[8] Oxley, J.: Matroid Theory. Oxford Graduate Texts in Mathematics 21, Oxford University Press, Oxford (2011). | DOI | MR | JFM

[9] Zaslavsky, T.: Signed graphs. Discrete Appl. Math. 4 (1982), 47-74 erratum ibid. 5 1983 248. | DOI | MR | JFM

[10] Zaslavsky, T.: Orientation of signed graphs. Eur. J. Comb. 12 (1991), 361-375. | DOI | MR | JFM

Cité par Sources :