Title
Bijections for the numeric representation of labeled graphs
Date Issued
01 January 2014
Access level
metadata only access
Resource Type
conference paper
Author(s)
Toyota Technological Institute
Publisher(s)
Institute of Electrical and Electronics Engineers Inc.
Abstract
Graphs denote useful dependencies among objects ubiquitously. This paper introduces new and simple bijections to the integer grid to enable the succinct, canonical and efficient representations of labeled graphs; whereas previous work has focused on regularities in structure such as triangularity, separability, planarity, symmetry and sparsity. By succinct we imply that space is information-theoretically optimal, by canonical we imply that generation of instances is unique, and by efficient we imply that coding and decoding take polynomial time. Our results have direct implications to handle labeled graphs by using single numbers efficiently, which is significant to enable the canonical graph encodings in learning and optimization algorithms. Our bijections are the first known in the literature.
Start page
447
End page
452
Volume
2014-January
Issue
January
Language
English
OCDE Knowledge area
Ciencias de la información
Mecánica aplicada
Scopus EID
2-s2.0-84938084162
ISSN of the container
1062922X
Conference
Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics
Sources of information:
Directorio de Producción CientÃfica
Scopus