Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.16186 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910136857001984 |
|---|---|
| author | Lindeberg, Anna Schmidt, Bruno J. Changat, Manoj Shanavas, Ameera Vaheeda Stadler, Peter F. Hellmuth, Marc |
| author_facet | Lindeberg, Anna Schmidt, Bruno J. Changat, Manoj Shanavas, Ameera Vaheeda Stadler, Peter F. Hellmuth, Marc |
| contents | Directed acyclic graphs (DAGs) are fundamental structures used across many scientific fields. A key concept in DAGs is the least common ancestor (LCA), which plays a crucial role in understanding hierarchical relationships. Surprisingly little attention has been given to DAGs that admit a unique LCA for every subset of their vertices. Here, we characterize such global lca-DAGs and provide multiple structural and combinatorial characterizations. We show that global lca-DAGs have a close connection to join semi-lattices and establish a connection to forbidden topological minors. In addition, we introduce a constructive approach to generating global lca-DAGs and demonstrate that they can be recognized in polynomial time. We investigate their relationship to clustering systems and other set systems derived from the underlying DAGs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_16186 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Global Least Common Ancestor (LCA) Networks Lindeberg, Anna Schmidt, Bruno J. Changat, Manoj Shanavas, Ameera Vaheeda Stadler, Peter F. Hellmuth, Marc Combinatorics Directed acyclic graphs (DAGs) are fundamental structures used across many scientific fields. A key concept in DAGs is the least common ancestor (LCA), which plays a crucial role in understanding hierarchical relationships. Surprisingly little attention has been given to DAGs that admit a unique LCA for every subset of their vertices. Here, we characterize such global lca-DAGs and provide multiple structural and combinatorial characterizations. We show that global lca-DAGs have a close connection to join semi-lattices and establish a connection to forbidden topological minors. In addition, we introduce a constructive approach to generating global lca-DAGs and demonstrate that they can be recognized in polynomial time. We investigate their relationship to clustering systems and other set systems derived from the underlying DAGs. |
| title | Global Least Common Ancestor (LCA) Networks |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.16186 |