Please use this identifier to cite or link to this item:
Type: Artigo
Title: Directed intersection representations and the information content of digraphs
Author: Liu, Xujun
Machado, Roberto Assis
Milenkovic, Olgica
Abstract: 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
Subject: Teoria dos conjuntos
Country: Estados Unidos
Editor: Institute of Electrical and Electronics Engineers
Rights: Fechado
Identifier DOI: 10.1109/TIT.2020.3033168
Date Issue: 2021
Appears in Collections:IMECC - Artigos e Outros Documentos

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.