Bijective Linear Time Coding and Decoding for k-Trees |
| |
Authors: | Saverio Caminiti Emanuele G Fusco Rossella Petreschi |
| |
Affiliation: | 1. Computer Science Department, University of Rome “La Sapienza”, via Salaria, 113-00198, Rome, Italy
|
| |
Abstract: | The problem of coding labeled trees has been widely studied in the literature and several bijective codes that realize associations
between labeled trees and sequences of labels have been presented. k-trees are one of the most natural and interesting generalizations of trees and there is considerable interest in developing
efficient tools to manipulate this class of graphs, since many NP-Complete problems have been shown to be polynomially solvable
on k-trees and partial k-trees. In 1970 Rényi and Rényi generalized the Prüfer code, the first bijective code for trees, to a subset of labeled k-trees. Subsequently, non redundant codes that realize bijection between k-trees (or Rényi k-trees) and a well defined set of strings were produced. In this paper we introduce a new bijective code for labeled k-trees which, to the best of our knowledge, produces the first coding and decoding algorithms running in linear time with
respect to the size of the k-tree. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|