Finding Shorter Cycles in a Weighted Graph

Autor: Ni Cao, Fugang Chao, Han Ren
Rok vydání: 2015
Předmět:
Zdroj: Graphs and Combinatorics. 32:65-77
ISSN: 1435-5914
0911-0119
DOI: 10.1007/s00373-015-1576-8
Popis: In this paper we investigate the structures of short cycles in a weighted graph. By Thomassen's $$3$$3-path-condition theory (Thomassen in J Comb Theory Ser 48:155---177, 1990), it is easy to find a shortest cycle in a collection of cycles beyond a subspace of the cycle space of a graph. What is more difficult for one to do is to find a shortest cycle within a subspace of the cycle space in polynomial time. By using the Dijkstra's algorithm (Dijkstra in Numer Math 1:55---61, 1959) we find a collection $$\mathcal {C}$$C of cycles containing many types of short cycles within a given subspace of the cycle space of a graph and this implies a polynomial time algorithm (called extended fundamental cycle algorithm) to locate all the possible shortest cycles in a weighted graph. In the case of unweighted graphs, the algorithm may also find every shortest even cycle in a graph, this greatly improved a result of Grotschel and Pulleyblank (Oper Res Lett 1:23---27, 1981/82), Monien (Computing 31:355---369, 1983), Yuster and Zwick (SIAM J Discrete Math 10:209---222, 1997). In fact, our algorithm shows that there are at most $$O(n^4)$$O(n4) many such short cycles in an unweighted graph of order $$n$$n. Further more, our fundamental cycle method may find a minimum cycle base (or simply MCB as some scholars named) in the cycle space of a graph. Since the structure of MCB's is unique (Ren and Deng in Discrete Math 307:2654---2660, 2007), this shows that, in the sense, cycles in a MCB are nearly-fundamental (i.e., each element in a MCB is a sum of at most two fundamental cycles). This provides a new way to study MCB.
Databáze: OpenAIRE
Externí odkaz: