Fast generation of ordered graphs with simple edge changes
Generating cyclic pivot Gray codes for well-ordered $k$-degenerate graphs in constant amortized time
Data Structures and Algorithms
Summary
Sometimes, it's important to list all graphs that follow certain rules, changing only one connection at a time, to understand their structure or find patterns quickly. The authors describe a new method that can do this for a special kind of graph called well-ordered k-degenerate graphs. Their approach creates each graph step-by-step very efficiently, using constant average time, and includes ways to find a graph's position in the list or get a graph from a position. This makes it easier to explore such graphs systematically.
What this means in practice
- •For network algorithm engineers: Generate all constrained network topologies efficiently to test dynamic routing and fault tolerance under incremental connection changes.
- •For graph database developers: Support fast indexing and retrieval of graphs by their position in a well-ordered k-degenerate family to improve query optimization.
Authors
Lei Dong, Dennis Wong, Bowie Liu, Rui Bao, Lin Chen, Chan-Tong Lam, Sio-Kei Im
Abstract
A graph $G$ is $k$-degenerate if there exists an ordering $v_1, v_2, \dots, v_n$ of its vertices such that each vertex $v_i$ has at most $k$ neighbors $v_j$ in $G$ with $j < i$. A well-ordered $k$-degenerate graph is a labeled graph on the vertex set $\{1, 2, \dots, n\}$ in which every vertex $i$ has at most $k$ neighbors among $1, 2, \dots, i-1$. We present the first simple algorithms that generate, rank, and unrank cyclic pivot Gray codes for well-ordered $k$-degenerate graphs, where consecutive graphs differ by the addition, removal, or pivoting of a single edge. Our algorithm generates each well-ordered $k$-degenerate graph in constant amortized time per graph, using $O(n^2)$ space, while ranking and unranking take $O(n^2)$ time and $O(n^2)$ space.