| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [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
Total Affiliations: 3
|
| Document type: | Journal article |
| Source: | IEEE TRANSACTIONS ON INFORMATION THEORY; v. 67, n. 1, p. 347-357, JAN 2021. |
| Web of Science Citations: | 0 |
| 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. (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 |