Bijections for the numeric representation of labeled graphs
Bijections for the numeric representation of labeled graphs
复制标题
用于标记图的数字表示的双射
DOI：
10.1109/smc.2014.6973948
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. Higashi
中科院分区：
文献类型：
--
作者：
V. Parque;Masakazu Kobayashi;M. Higashi
图表示对象之间普遍存在的有用依赖关系。本文介绍了新的和简单的双射的整数网格，使简洁，规范和有效的表示标记图，而以前的工作主要集中在网络结构，如三角形，可分性，平面性，对称性和稀疏性。简洁意味着空间是信息理论上最优的，规范意味着实例的生成是唯一的，高效意味着编码和解码需要多项式时间。我们的研究结果对于有效地使用单个数来处理标记图具有直接的意义，这对于在学习和优化算法中实现正则图编码具有重要意义。我们的双射是文献中第一个已知的。
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.