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, 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 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 encoding and decoding algorithms running in linear time with respect to the size of the k-tree. © Springer-Verlag Berlin Heidelberg 2007.

A bijective code for k-trees with linear time encoding and decoding / Caminiti, Saverio; Fusco, EMANUELE GUIDO; Petreschi, Rossella. - STAMPA. - 4614:(2007), pp. 408-420. (Intervento presentato al convegno 1st International Conference on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies tenutosi a Hangzhou, PEOPLES R CHINA nel APR 07-09, 2007) [10.1007/978-3-540-74450-4_37].

A bijective code for k-trees with linear time encoding and decoding

CAMINITI, SAVERIO;FUSCO, EMANUELE GUIDO;PETRESCHI, Rossella
2007

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, 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 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 encoding and decoding algorithms running in linear time with respect to the size of the k-tree. © Springer-Verlag Berlin Heidelberg 2007.
2007
1st International Conference on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies
bijective codes; k-tree; linear time algorithms
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
A bijective code for k-trees with linear time encoding and decoding / Caminiti, Saverio; Fusco, EMANUELE GUIDO; Petreschi, Rossella. - STAMPA. - 4614:(2007), pp. 408-420. (Intervento presentato al convegno 1st International Conference on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies tenutosi a Hangzhou, PEOPLES R CHINA nel APR 07-09, 2007) [10.1007/978-3-540-74450-4_37].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/367171
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact