𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Computer program for finding all possible cycles in graphs

✍ Scribed by Alexandru T. Balaban; Petru Filip; Teodor-Silviu Balaban

Publisher
John Wiley and Sons
Year
1985
Tongue
English
Weight
703 KB
Volume
6
Category
Article
ISSN
0192-8651

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A new approach is presented for identifying all possible cycles in graphs. Input data are the total numbers of vertices and edges, as well as the vertex adjacencies using arbitrary vertex numbering. A homeomorphically reduced graph (HRG) is constructed by ignoring vertices of degree less than three. The algorithm is based on successive generation of possible edge‐combinations in the HRG. If a combination yields a cycle, it is either printed or stored and then finally printed in a list of all possible cycles arranged in the order of increasing ring size. A unique numbering of the cycle is used. The computer program is listed and exemplified. Computing times are given.

πŸ“œ SIMILAR VOLUMES

A linear-time algorithm for computing th
A linear-time algorithm for computing the intersection of all odd cycles in a graph
✍ Leizhen Cai; Baruch Schieber πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 506 KB

We present a linear-time algorithm that finds all edges and vertices in the intersection of all odd cycles in a given graph. We also show an application of our algorithm to a variant of the satisfiability problem of Boolean formulas.

A comparison of three algorithms for fin
A comparison of three algorithms for finding fundamental cycles in a directed graph
✍ Doris R. Ryan; Stephen Chen πŸ“‚ Article πŸ“… 1981 πŸ› John Wiley and Sons 🌐 English βš– 543 KB

## Abstract Given a connected directed graph and a spanning tree, we consider the problem of finding the set of fundamental cycles. In particular, for each cotree arc __i__ and tree arc __j__, we need to know whether or not __i__ and __j__ are in the same fundamental cycle, and if so, whether or no