information:extraction, information:highlighting, structural:summarization
Computation

The girth of an undirected graph can be computed by running a breadth-first search from each node, with complexity O (n m) {\displaystyle O(nm)} where n {\displaystyle n} is the number of vertices of the graph and m {\displaystyle m} is the number of edges. A practical optimization is to limit the depth of the BFS to a depth that depends on the length of the smallest cycle discovered so far. Better algorithms are known in the case where the girth is even and when the graph is planar. In terms of lower bounds, computing the girth of a graph is at least as hard as solving the triangle finding problem on the graph.