Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion

Journal of Discrete Algorithms - Tập 6 - Trang 93-102 - 2008
Marcel Wild1
1Department of Mathematical Sciences, University of Stellenbosch, Van der Ster Gebou, kamer 2023, 7602 Stellenbosch, South Africa

Tài liệu tham khảo

Gibbs, 1969, A cycle generation algorithm for finite undirected linear graphs, J. Assoc. Comput. Mach., 16, 564, 10.1145/321541.321545 Jackowski, 1993, Methods for determining all the chordless cycles of a bipartite graph and for testing whether a binary matrix is balanced, Arch. Control Sci., 2, 55 Bang-Jensen, 2001 Mateti, 1976, On algorithms for enumerating all circuits of a graph, SIAM J. Comput., 5, 90, 10.1137/0205007 Read, 1975, Bounds on backtrack algorithms for listing cycles, paths, and spanning trees, Networks, 5, 237, 10.1002/net.1975.5.3.237 Schrijver, 2003 Syslo, 1981, An efficient cycle vector space algorithm for listing all cycles of a planar graph, SIAM J. Comput., 10, 797, 10.1137/0210062 Welch, 1966, A mechanical analysis of the cyclic structure of undirected linear graphs, J. Assoc. Comput. Mech., 13, 205, 10.1145/321328.321331 M. Wild, Generating all perfect matchings of a not necessarily bipartite graph, in preparation