Directed Intersection Representations and the Information Content of Digraphs

Autor(es)

Liu, Xujun ^[1] ; Machado, Roberto Assis ^[2] ; Milenkovic, Olgica ^[3]

Afiliação do(s) autor(es)

^[1] Univ Illinois, Dept Math, Champaign, IL 61801 - USA

^[2] Univ Estadual Campinas, Dept Math, BR-13083970 Campinas - Brazil

^[3] Univ Illinois, Dept Elect & Comp Engn, Champaign, IL 61801 - USA

• Tipo de documento: Artigo Científico
• Fonte: IEEE TRANSACTIONS ON INFORMATION THEORY; v. 67, n. 1, p. 347-357, JAN 2021.
• Citações Web of Science: 0

Resumo

Consider a directed graph (digraph) in which vertices are assigned color sets, and two vertices are connected if and only if they share at least one color and the tail vertex has a strictly smaller color set than the head. We seek to determine the smallest possible size of the union of the color sets that allows for such a digraph representation. 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 introduce the directed intersection number (DIN), the smallest number of colors needed to represent a DAG. Our main results are upper bounds on the DIN of DAGs based on what we call the longest terminal path decomposition of the vertex set, and constructive lower bounds. (AU)

• Processo FAPESP: 15/11286-8 - Métricas que respeitam suporte e decodificação de máxima proximidade
• Beneficiário: Roberto Assis Machado
• Modalidade de apoio: Bolsas no Brasil - Doutorado