1. Coding Properties of Breadth-First Search Orderings
- Author
-
P. Ossona de Mendez and P. Rosenstiehl
- Subjects
Discrete mathematics ,Combinatorics ,Applied Mathematics ,Breadth-first search ,Bijection ,Discrete Mathematics and Combinatorics ,Reciprocal ,Mathematics ,Coding (social sciences) - Abstract
Though it is known for long that there is as many pointed maps with m edges as connected involutions on {1,…, 2m + 2}, no actual bijection were known between these combinatorial objects. Such a bijection is described here as two reciprocal constructions: a map encoding and a map construction. These constructions appear to be simply derived from the properties of breadth-first search orderings.
- Published
- 2000
- Full Text
- View/download PDF