Back to Search
Start Over
Family Trees for Enumeration.
- Source :
-
International Journal of Foundations of Computer Science . Nov2023, Vol. 34 Issue 7, p715-736. 22p. - Publication Year :
- 2023
-
Abstract
- In this paper we design efficient algorithms for enumerating (1) the rooted trees with exactly n vertices, (2) the maximal planar graphs with exactly n vertices and (3) the linear extensions of a given poset. Those algorithms are based on tree structures of objects, called the family trees. The first algorithm enumerates each ordered tree with exactly n vertices in O (1) time for each after O (n) time preprocessing. The second algorithm enumerates each maximal planar graph with exactly n vertices in O (n 3) time for each on average. The third algorithm enumerates each linear extension of a given poset in O (1) time for each after O (n 2) time preprocessing, where n is the number of the element in the set of the poset. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GENEALOGY
*PLANAR graphs
*MULTICASTING (Computer networks)
Subjects
Details
- Language :
- English
- ISSN :
- 01290541
- Volume :
- 34
- Issue :
- 7
- Database :
- Academic Search Index
- Journal :
- International Journal of Foundations of Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 173182847
- Full Text :
- https://doi.org/10.1142/S0129054123420078