2017 · 22 citations · 17 references
ComputingComputer ScienceAlgorithmsData StructuresKnowledge RepresentationDirected Acyclic GraphsGraph AlgorithmsGraph TheoryGraph-based LearningGraphical RepresentationDigraph RepresentationDirected GraphsGraph OptimizationGraph Representation LearningLabeled Graph RepresentationsOptimization AlgorithmsPolynomial Time ComplexityPolynomial-time Algorithms
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.
17
A Dynamic Survey of Graph Labeling
Joseph A. Gallian · The Electronic Journal of Combinatorics · 2022 · 2.2K citations · Full text
Space-efficient static trees and graphs
G. Jacobson · 1989 · 649 citations
Paolo Boldi, Marco Rosa, Massimo Santini et al. · 2011 · 606 citations
Succinct representations of graphs
Hana Galperin, Avi Wigderson · Information and Control · 1983 · 219 citations