Mathematics – Combinatorics
Scientific paper
2007-06-07
Theoretical Computer Science Volume 411, Issues 31-33, 28 June 2010, Pages 2945-2967
Mathematics
Combinatorics
29 pages, over 140 drawings
Scientific paper
A trivalent diagram is a connected, two-colored bipartite graph (parallel edges allowed but not loops) such that every black vertex is of degree 1 or 3 and every white vertex is of degree 1 or 2, with a cyclic order imposed on every set of edges incident to to a same vertex. A rooted trivalent diagram is a trivalent diagram with a distinguished edge, its root. We shall describe and analyze an algorithm giving an exhaustive list of rooted trivalent diagrams of a given size (number of edges), the list being non-redundant in that no two diagrams of the list are isomorphic. The algorithm will be shown to have optimal performance in that the time necessary to generate a diagram will be seen to be bounded in the amortized sense, the bound being independent of the size of the diagrams. That's what we call the CAT property. One objective of the paper is to provide a reusable theoretical framework for algorithms generating exhaustive lists of complex combinatorial structures with attention paid to the case of unlabeled structures and to those generators having the CAT property.
No associations
LandOfFree
An Optimal Algorithm to Generate Pointed Trivalent Diagrams and Pointed Triangular Maps does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Optimal Algorithm to Generate Pointed Trivalent Diagrams and Pointed Triangular Maps, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Optimal Algorithm to Generate Pointed Trivalent Diagrams and Pointed Triangular Maps will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-442049