Transitive closure and transitive reduction in bidirected graphs
Ouahiba Bessouf; Abdelkader Khelladi; Thomas Zaslavsky
Czechoslovak Mathematical Journal (2019)
- Volume: 69, Issue: 2, page 295-315
- ISSN: 0011-4642
Access Full Article
top
Abstract
topHow to cite
topBessouf, Ouahiba, Khelladi, Abdelkader, and Zaslavsky, Thomas. "Transitive closure and transitive reduction in bidirected graphs." Czechoslovak Mathematical Journal 69.2 (2019): 295-315. <http://eudml.org/doc/294557>.
@article{Bessouf2019,
abstract = {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.},
author = {Bessouf, Ouahiba, Khelladi, Abdelkader, Zaslavsky, Thomas},
journal = {Czechoslovak Mathematical Journal},
keywords = {bidirected graph; signed graph; matroid; transitive closure; transitive reduction},
language = {eng},
number = {2},
pages = {295-315},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Transitive closure and transitive reduction in bidirected graphs},
url = {http://eudml.org/doc/294557},
volume = {69},
year = {2019},
}
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
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 69
IS - 2
SP - 295
EP - 315
AB - 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.
LA - eng
KW - bidirected graph; signed graph; matroid; transitive closure; transitive reduction
UR - http://eudml.org/doc/294557
ER -
References
top- Aho, A. V., Garey, M. R., Ullman, J. D., 10.1137/0201008, SIAM J. Comput. 1 (1972), 131-137. (1972) Zbl0247.05128MR0306032DOI10.1137/0201008
- Berge, C., Théorie des graphes et ses applications, Collection Universitaire de Mathématiques, 2, Dunod, Paris French (1958). (1958) Zbl0088.15404MR0102822
- 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). (1999)
- Harary, F., 10.1307/mmj/1028989917, Mich. Math. J. 2 (1954), 143-146. (1954) Zbl0056.42103MR0067468DOI10.1307/mmj/1028989917
- Harary, F., 10.1002/bs.3830020403, Behavioral Sci. 2 (1957), 255-265. (1957) MR0134799DOI10.1002/bs.3830020403
- 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). (1985)
- Khelladi, A., 10.1016/0095-8956(87)90032-3, J. Comb. Theory, Ser. B 43 (1987), 95-115. (1987) Zbl0617.90026MR0897242DOI10.1016/0095-8956(87)90032-3
- Oxley, J., 10.1093/acprof:oso/9780198566946.001.0001, Oxford Graduate Texts in Mathematics 21, Oxford University Press, Oxford (2011). (2011) Zbl1254.05002MR2849819DOI10.1093/acprof:oso/9780198566946.001.0001
- Zaslavsky, T., 10.1016/0166-218X(83)90047-1, Discrete Appl. Math. 4 (1982), 47-74 erratum ibid. 5 1983 248. (1982) Zbl0503.05060MR0683518DOI10.1016/0166-218X(83)90047-1
- Zaslavsky, T., 10.1016/S0195-6698(13)80118-7, Eur. J. Comb. 12 (1991), 361-375. (1991) Zbl0761.05095MR1120422DOI10.1016/S0195-6698(13)80118-7
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.