Chordless cycles are very natural structures in undirected graphs, with an important history and distinguished role in graph theory. Motivated also by previous work on the classical problem of listing cycles, we study how to list chordless cycles. The best known solution to list all the C chordless cycles contained in an undirected graph G = (V,E) takes O(|E|2 + |E| ·C) time. In this paper we provide an algorithm taking Õ (|E|+|V|⋅C) time. We also show how to obtain the same complexity for listing all the P chordless st-paths in G (where C is replaced by P).

Amortized \~O(\(\vert\)V\(\vert\)) -Delay Algorithm for Listing Chordless Cycles in Undirected Graphs

RIZZI, ROMEO;
2014-01-01

Abstract

Chordless cycles are very natural structures in undirected graphs, with an important history and distinguished role in graph theory. Motivated also by previous work on the classical problem of listing cycles, we study how to list chordless cycles. The best known solution to list all the C chordless cycles contained in an undirected graph G = (V,E) takes O(|E|2 + |E| ·C) time. In this paper we provide an algorithm taking Õ (|E|+|V|⋅C) time. We also show how to obtain the same complexity for listing all the P chordless st-paths in G (where C is replaced by P).
2014
978-3-662-44776-5
listing, chordless cycles, chordless st-paths
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11562/933309
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 8
social impact