On succinct representation of directed graphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

23 Citations (Scopus)

Abstract

Directed graphs encode meaningful dependencies among objects ubiquitously. This paper introduces new and simple representations for labeled directed graphs with the properties of being succinct (space is information-theoretically optimal); in which we avoid exploiting a-priori knowledge on digraph regularity such as triangularity, separability, planarity, symmetry and sparsity. Our results have direct implications to model directed graphs by using single integer numbers effectively, which is significant to enable canonical (generation of graph instances is unique) and efficient (coding and decoding take polynomial time) encodings for learning and optimization algorithms. To the best of our knowledge, the proposed representations are the first known in the literature.

Original languageEnglish
Title of host publication2017 IEEE International Conference on Big Data and Smart Computing, BigComp 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages199-205
Number of pages7
ISBN (Electronic)9781509030156
DOIs
Publication statusPublished - 2017 Mar 17
Event2017 IEEE International Conference on Big Data and Smart Computing, BigComp 2017 - Jeju Island, Korea, Republic of
Duration: 2017 Feb 132017 Feb 16

Publication series

Name2017 IEEE International Conference on Big Data and Smart Computing, BigComp 2017

Other

Other2017 IEEE International Conference on Big Data and Smart Computing, BigComp 2017
Country/TerritoryKorea, Republic of
CityJeju Island
Period17/2/1317/2/16

ASJC Scopus subject areas

  • Information Systems
  • Artificial Intelligence
  • Computer Science Applications
  • Computer Vision and Pattern Recognition

Fingerprint

Dive into the research topics of 'On succinct representation of directed graphs'. Together they form a unique fingerprint.

Cite this