Editing Girth (graph theory) (section)

== Computation ==

The girth of an undirected graph can be computed by running a [[breadth-first search]] from each node, with complexity <math>O(nm)</math> where <math>n</math> is the number of vertices of the graph and <math>m</math> is the number of edges.<ref>{{Cite web |url=http://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf |title=Question 3: Computing the girth of a graph |access-date=February 22, 2023 |archive-date=August 29, 2017 |archive-url=https://web.archive.org/web/20170829175217/http://webcourse.cs.technion.ac.il/234247/Winter2003-2004/ho/WCFiles/Girth.pdf |url-status=dead }}</ref> 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.<ref>{{Cite web |last=Völkel |first=Christoph Dürr, Louis Abraham and Finn |date=2016-11-06 |title=Shortest cycle |url=https://tryalgo.org/en/cycles/2016/11/06/shortest-cycle/ |access-date=2023-02-22 |website=TryAlgo |language=en-US}}</ref> Better algorithms are known in the case where the girth is even<ref>{{Cite web |title=ds.algorithms - Optimal algorithm for finding the girth of a sparse graph? |url=https://cstheory.stackexchange.com/questions/10983/optimal-algorithm-for-finding-the-girth-of-a-sparse-graph |access-date=2023-02-22 |website=Theoretical Computer Science Stack Exchange |language=en}}</ref> and when the graph is planar.<ref>{{Cite journal |last1=Chang |first1=Hsien-Chih |last2=Lu |first2=Hsueh-I. |date=2013 |title=Computing the Girth of a Planar Graph in Linear Time |journal=SIAM Journal on Computing |volume=42 |issue=3 |pages=1077–1094 |doi=10.1137/110832033 |arxiv=1104.4892 |s2cid=2493979 |issn=0097-5397}}</ref> 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.