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:
| Main Authors: | , , |
|---|---|
| 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!
|