Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Unique Least Common Ancestors and Clusters in Directed Acyclic Graphs
Stockholm University, Faculty of Science, Department of Mathematics.ORCID iD: 0000-0002-1620-5508
Number of Authors: 42024 (English)In: Algorithms and Discrete Applied Mathematics: Proceedings / [ed] Subrahmanyam Kalyanasundaram, Anil Maheshwari, Springer, 2024, p. 148-161Conference paper, Published paper (Refereed)
Abstract [en]

We investigate the connections between clusters and least common ancestors (LCAs) in directed acyclic graphs (DAGs). We focus on the class of DAGs having unique least common ancestors for certain subsets of their minimal elements since these are of interest, particularly as models of phylogenetic networks. Here, we use the close connection between the canonical k-ary transit function and the closure function on a set system to show that pre-k-ary clustering systems are exactly those that derive from a class of DAGs with unique LCAs. Moreover, we show that k-ary T -systems and k-weak hierarchies are associated with DAGs that satisfy stronger conditions on the existence of unique LCAs for sets of size at most k.

Place, publisher, year, edition, pages
Springer, 2024. p. 148-161
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743, E-ISSN 1611-3349 ; 14508 LNCS
Keywords [en]
closure function, clustering system, k-weak hierarchy, Monotone transit function
National Category
Computational Mathematics
Identifiers
URN: urn:nbn:se:su:diva-236606DOI: 10.1007/978-3-031-52213-0_11ISI: 001207825300011Scopus ID: 2-s2.0-85184094423ISBN: 9783031522123 (print)OAI: oai:DiVA.org:su-236606DiVA, id: diva2:1917875
Conference
10th International Conference, CALDAM 2024, Bhilai, India, February 15–17, 2024
Available from: 2024-12-03 Created: 2024-12-03 Last updated: 2024-12-03Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Hellmuth, Marc

Search in DiVA

By author/editor
Hellmuth, Marc
By organisation
Department of Mathematics
Computational Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 23 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf