| Full text | |
| Author(s): |
Koslochka, Alexandr V.
;
Liu, Xujun
;
Machado, Roberto
;
Milenkovic, Olgica
;
IEEE
Total Authors: 5
|
| Document type: | Journal article |
| Source: | 2019 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT); v. N/A, p. 5-pg., 2019-01-01. |
| Abstract | |
Consider a directed graph (digraph) in which two user vertices are connected if and only if they share at least one unit of common information content and the head vertex has a strictly smaller content than the tail. We seek to estimate the smallest possible global information content that can explain the observed digraph topology. To address this problem, we introduce the new notion of a directed intersection representation of a digraph, and show that it is well-defined for all directed acyclic graphs (DAGs). We then proceed to describe the directed intersection number (DIN), the smallest number of information units needed to represent the DAG. Our main result is a nontrivial upper bound on the DIN number of DAGs based on the longest terminal path decomposition of the vertex set. In addition, we compute the exact values of the DIN number for several simple yet relevant families of connected DAGs and construct digraphs that have near-optimal DIN values. (AU) | |
| FAPESP's process: | 15/11286-8 - Metrics that agree on the support of vectors and nearest neighbor decoding |
| Grantee: | Roberto Assis Machado |
| Support Opportunities: | Scholarships in Brazil - Doctorate |