A compact code for k-trees

A compact code for k-trees

In this paper, we propose a new representation for k-trees - the compact code, which reduces the required memory space from O(nk) to O(n). The encoding and decoding algorithms, based on a simplification of a priority queue, are linear and very simple. As long as the k-tree is represented by its compact code, the exact vertex coloring problem can be solved in time O(n).

Saved in:
Bibliographic Details
Main Authors: Markenzon,Lilian, Vernet,Oswaldo, Pereira,Paulo Renato da Costa
Format: Digital revista
Language:English
Published: Sociedade Brasileira de Pesquisa Operacional 2009
Online Access:http://old.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382009000300001
Tags: Add Tag
No Tags, Be the first to tag this record!
id oai:scielo:S0101-74382009000300001
record_format ojs
spelling oai:scielo:S0101-743820090003000012010-02-03A compact code for k-treesMarkenzon,LilianVernet,OswaldoPereira,Paulo Renato da Costa k-trees Prüfer code compact code In this paper, we propose a new representation for k-trees - the compact code, which reduces the required memory space from O(nk) to O(n). The encoding and decoding algorithms, based on a simplification of a priority queue, are linear and very simple. As long as the k-tree is represented by its compact code, the exact vertex coloring problem can be solved in time O(n).info:eu-repo/semantics/openAccessSociedade Brasileira de Pesquisa OperacionalPesquisa Operacional v.29 n.3 20092009-12-01info:eu-repo/semantics/articletext/htmlhttp://old.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382009000300001en10.1590/S0101-74382009000300001
institution SCIELO
collection OJS
country Brasil
countrycode BR
component Revista
access En linea
databasecode rev-scielo-br
tag revista
region America del Sur
libraryname SciELO
language English
format Digital
author Markenzon,Lilian
Vernet,Oswaldo
Pereira,Paulo Renato da Costa
spellingShingle Markenzon,Lilian
Vernet,Oswaldo
Pereira,Paulo Renato da Costa
A compact code for k-trees
author_facet Markenzon,Lilian
Vernet,Oswaldo
Pereira,Paulo Renato da Costa
author_sort Markenzon,Lilian
title A compact code for k-trees
title_short A compact code for k-trees
title_full A compact code for k-trees
title_fullStr A compact code for k-trees
title_full_unstemmed A compact code for k-trees
title_sort compact code for k-trees
description In this paper, we propose a new representation for k-trees - the compact code, which reduces the required memory space from O(nk) to O(n). The encoding and decoding algorithms, based on a simplification of a priority queue, are linear and very simple. As long as the k-tree is represented by its compact code, the exact vertex coloring problem can be solved in time O(n).
publisher Sociedade Brasileira de Pesquisa Operacional
publishDate 2009
url http://old.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382009000300001
work_keys_str_mv AT markenzonlilian acompactcodeforktrees
AT vernetoswaldo acompactcodeforktrees
AT pereirapaulorenatodacosta acompactcodeforktrees
AT markenzonlilian compactcodeforktrees
AT vernetoswaldo compactcodeforktrees
AT pereirapaulorenatodacosta compactcodeforktrees
_version_ 1756394154361880576

Similar Items