Geodesic
Circuit bases of strongly connected digraphs
Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 241-260.

Voir la notice de l'article provenant de la source Library of Science

The cycle space of a strongly connected graph has a basis consisting of directed circuits. The concept of relevant circuits is introduced as a generalization of the relevant cycles in undirected graphs. A polynomial time algorithm for the computation of a minimum weight directed circuit basis is outlined.
Keywords: directed graphs, cycle space, relevant circuits, minimum length basis 
@article{DMGT_2003_23_2_a3,
     author = {Gleiss, Petra and Leydold, Josef and Stadler, Peter},
     title = {Circuit bases of strongly connected digraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {241--260},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2003},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a3/}
}
TY  - JOUR
AU  - Gleiss, Petra
AU  - Leydold, Josef
AU  - Stadler, Peter
TI  - Circuit bases of strongly connected digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2003
SP  - 241
EP  - 260
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a3/
LA  - en
ID  - DMGT_2003_23_2_a3
ER  - 
%0 Journal Article
%A Gleiss, Petra
%A Leydold, Josef
%A Stadler, Peter
%T Circuit bases of strongly connected digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2003
%P 241-260
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a3/
%G en
%F DMGT_2003_23_2_a3
Gleiss, Petra; Leydold, Josef; Stadler, Peter. Circuit bases of strongly connected digraphs. Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 241-260. http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a3/

[1] A.T. Balaban, D. Farcasiu, and R. B anica, Graphs of multiple 1,2-shifts in carbonium ions and related systems, Rev. Roum. Chem. 11 (1966) 1205-1227.

[2] R. Balducci and R.S. Pearlman, Efficient exact solution of the ring perception problem, J. Chem. Inf. Comput. Sci. 34 (1994) 822-831, doi: 10.1021/ci00020a016.

[3] C. Berge, Graphs (North-Holland, Amsterdam, NL, 1985).

[4] B. Bollobás, Modern Graph Theory (Springer, New York, 1998).

[5] L.O. Chua and L. Chen, On optimally sparse cycle and coboundary basis for a linear graph, IEEE Trans. Circuit Theory 20 (1973) 54-76.

[6] G.M. Downs, V.J. Gillet, J.D. Holliday and M.F. Lynch, Review of ring perception algorithms for chemical graphs, J. Chem. Inf. Comput. Sci. 29 (1989) 172-187, doi: 10.1021/ci00063a007.

[7] D.A. Fell, Understanding the Control of Metabolism (Portland Press, London, 1997).

[8] A. Galluccio and M. Loebl, (p,q)-odd graphs, J. Graph Theory 23 (1996) 175-184, doi: 10.1002/(SICI)1097-0118(199610)23:2175::AID-JGT8>3.0.CO;2-Q

[9] P.M. Gleiss, P.F. Stadler, A. Wagner and D.A. Fell, Relevant cycles in chemical reaction network, Adv. Cmplx. Syst. 4 (2001) 207-226, doi: 10.1142/S0219525901000140.

[10] M. Hartmann, H. Schneider and M.H. Schneider, Integral bases and p-twisted digraphs, Europ. J. Combinatorics 16 (1995) 357-369, doi: 10.1016/0195-6698(95)90017-9.

[11] D. Hartvigsen, Minimum path bases, J. Algorithms 15 (1993) 125-142, doi: 10.1006/jagm.1993.1033.

[12] D. Hartvigsen and R. Mardon, When do short cycles generate the cycle space, J. Combin. Theory (B) 57 (1993) 88-99, doi: 10.1006/jctb.1993.1008.

[13] D. Hartvigsen and R. Mardon, The all-pair min-cut problem and the minimum cycle basis problem on planar graphs, SIAM J. Discrete Math. 7 (1994) 403-418, doi: 10.1137/S0895480190177042.

[14] J.D. Horton, A polynomial-time algorithm to find the shortest cycle basis of a graph, SIAM J. Comput. 16 (1987) 359-366, doi: 10.1137/0216026.

[15] D.B. Johnson, Finding all the elementary circuits of a directed graph, SIAM J. Comput. 4 (1975) 77-84, doi: 10.1137/0204007.

[16] A. Kaveh, Structural Mechanics: Graph and Matrix Methods (Research Studies Press, Exeter, UK, 1992).

[17] J.B. Kruskal, On the shortest spanning subgraph of a graph and the travelling salesman problem, Proc. Amer. Math. Soc. 7 (1956) 48-49, doi: 10.1090/S0002-9939-1956-0078686-7.

[18] M. Las Vergnas, Sur le nombre de circuits dans un tournnoi fortement connexe, Cahiers C.E.R.O. 17 (1975) 261-265.

[19] D. Marcu, On finding the elementary paths and circuits of a digraph, Polytech. Univ. Bucharest Sci. Bull. Ser. D: Mech. Engrg. 55 (1993) 29-33.

[20] R.T. Rockafellar, Convex Analysis (Princeton Univ. Press, Princeton NJ, 1970).

[21] G.F. Stepanec, Basis systems of vector cycles with extremal properties in graphs, Uspekhi Mat. Nauk. 2, 19 (1964) 171-175 (Russian).

[22] K. Thulasiraman and M.N.S. Swamy, Graphs: Theory and Algorithms (J. Wiley Sons, New York, 1992), doi: 10.1002/9781118033104.

[23] P. Vismara, Reconnaissance et représentation d'éléments structuraux pour la description d'objets complexes, Application à l'élaboration de stratégies de synthèse en chimie organique (PhD thesis, Université Montpellier II, France, 1995) 95-MON-2-253.

[24] P. Vismara, Union of all the minimum cycle bases of a graph, Electr. J. Combin. 4 (1997) 73-87. Paper No. #R9 (15 pages).