We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Decomposition and Merging Algorithms for Noncrossing Forests.
- Authors
Pang, Sabrina X. M.; Lv, Lun; Deng, Xiaoming
- Abstract
A noncrossing forest is a forest drawn on n points numbered in counterclockwise order on a circle in such a way that its edges are rectilinear and do not cross. Utilizing analytic combinatorics, Flajolet and Noy obtained the number of noncrossing forests with n vertices and k components. In this paper, we will give a new representation for noncrossing forests. Based on such respresentation, we establish a decomposition algorithm and a merging algorithm, which leads to a bijection between labeled noncrossing forests and sets of rooted matches. As an application, we derive a new formula, which is a refinement of the formula given by Flajolet and Noy.
- Subjects
ALGORITHMS; COMBINATORICS; BIJECTIONS
- Publication
Graphs & Combinatorics, 2022, Vol 38, Issue 1, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-021-02415-5