Christian Lavault. A note on Prufer-like coding and counting forests of uniform hypertrees


Natural Sciences / Computer Science / Analysis of algorithms

Submitted on: May 03, 2012, 13:02:30

Description: This note presents an encoding and a decoding algorithms for a forest of (labelled) rooted uniform hypertrees and hypercycles in linear time, by using as few as n-2 integers in the range [1,n]. It is a simple extension of the classical Prufer code for (labelled) rooted trees to an encoding for forests of (labelled) rooted uniform hypertrees and hypercycles, which allows to count them up according to their number of vertices, hyperedges and hypertrees. In passing, we also find Cayley's formula for the number of (labelled) rooted trees as well as its generalisation to the number of hypercycles found by Selivanov in the early 70's.

The abstract of this article has been published in the "Intellectual Archive Bulletin" , May 2012, ISSN 1929-1329.

The Library and Archives Canada reference page: collectionscanada.gc.ca/ourl/res.php?url_ver=Z39.88......

To read the article posted on Intellectual Archive web site please click the link below.

Christian_Lavault__Prufer-like_coding.pdf



© 2011-2017 Shiny World Corp. All rights reserved. To reach us please send an e-mail to support@IntellectualArchive.com