pipette
ESEspañol

Generating cyclic pivot Gray codes for well-ordered -degenerate graphs in constant amortized time

Lei Dong, Dennis Wong, Bowie Liu, Rui Bao, Lin Chen, Chan-Tong Lam, Sio-Kei Im

Preprint

In the authors' words

A graph is -degenerate if there exists an ordering of its vertices such that each vertex has at most neighbors in with . A well-ordered -degenerate graph is a labeled graph on the vertex set in which every vertex has at most neighbors among . We present the first simple algorithms that generate, rank, and unrank cyclic pivot Gray codes for well-ordered -degenerate graphs, where consecutive graphs differ by the addition, removal, or pivoting of a single edge. Our algorithm generates each well-ordered -degenerate graph in constant amortized time per graph, using space, while ranking and unranking take time and space.

Main resultThe abstract does not state a limitation.

Appeared: Thursday, October 8. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 38 pages, 4 figures