Directed Intersection Representations and the Information Content of Digraphs

Alexandr V. Kostochka, Xujun Liu, Roberto Machado, Olgica Milenkovic

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

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.

Original languageEnglish (US)
Title of host publication2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1477-1481
Number of pages5
ISBN (Electronic)9781538692912
DOIs
StatePublished - Jul 2019
Event2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France
Duration: Jul 7 2019Jul 12 2019

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
Volume2019-July
ISSN (Print)2157-8095

Conference

Conference2019 IEEE International Symposium on Information Theory, ISIT 2019
CountryFrance
CityParis
Period7/7/197/12/19

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Directed Intersection Representations and the Information Content of Digraphs'. Together they form a unique fingerprint.

Cite this