Title
On the numerical representation of labeled graphs with self-loops
Date Issued
04 June 2018
Access level
metadata only access
Resource Type
conference paper
Author(s)
Waseda University
Publisher(s)
IEEE Computer Society
Abstract
Graphs with self-loops enable to represent a large variety of interactions in natural and artificial systems, allowing not only inter-connectivity among heterogeneous entities but also the self-dependence of entities, e.g.The recursive and autonomous nature of dynamical systems. In this paper we present new bijective constructs which enable the numerical representation of graphs with self loops (or loopy graphs). In particular, we study the case of (1) undirected and (2) directed graphs with n nodes and m edges with self-loops. Our proposed approach realizes the succinct representations by using integer numbers in which rigorous computational experiments show the efficiency of our proposed algorithms: The complexity follows a quasi-linear behaviour as a function of the number of edges (which is independent of the number of nodes). Furthermore, as direct consequence of our constructs, we propose list structures having O(m) space complexity, which realize the linear space complexity depending only on the number of edges (the list is independent of n). We believe that our bijective algorithms are useful to tackle problems involving sampling of graphical models, network design as well as process planning by using number theory and sample-based learning.
Start page
342
End page
349
Volume
2017-November
Language
English
OCDE Knowledge area
Matemáticas puras Ingeniería de sistemas y comunicaciones
Scopus EID
2-s2.0-85048473914
ISSN of the container
10823409
ISBN of the container
9781538638767
Conference
Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI
Sources of information: Directorio de Producción Científica Scopus