Computational Science Technical Note CSTN-013

CSTN Home

Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs

K. A. Hawick and H. A. James

Archived February 2005, Updated March 2008

Abstract

The problems of detecting and enumerating circuits in graphs and networks are still of fundamental importance. We extend the circuit enumeration algorithm of Johnson for graphs with directed-arcs, multiple-arcs and self-arcs and present a memory efficient and high-performance implementation in the D programming language. We also discuss other circuit applications including how the code could be adapted as a cycle detection algorithm.

Keywords: graph; circuit; enumeration; algorithm.

Full Document Text: PDF version.

Full Document Text:

Citation Information: BiBTeX database for CSTN Notes.

BiBTeX reference:

@INPROCEEDINGS{CSTN-013,
  author = {K. A. Hawick and H. A. James},
  title = {Enumerating Circuits and Loops in Graphs with Self-Arcs and Multiple-Arcs},
  booktitle = {Proc. 2008 Int. Conf. on Foundations of Computer Science (FCS'08)},
  year = {2008},
  pages = {14-20},
  address = {Las Vegas, USA},
  month = {14-17 July},
  publisher = {CSREA},
  institution = {{Massey University}},
  timestamp = {2007.07.12}
}


[ CSTN Index | CSTN BiBTeX ]