An Efficient Computation of the Rank Function of a Positroid
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
Positroids are a class of matroids in bijection with several combinatorial objects. In particular, every positroid can be constructed from a decorated permutation or from a Le-graph. In this paper, we present two algorithms, one that computes the rank of a subset of a positroid using its representation as a Le-graph and the other takes as input a decorated permutation σ and outputs the Le-graph that represent the same positroid as σ. These two algorithms combined form an improvement to Mcalmon and Oh’s result on the computation of the rank function of a positroid from the decorated permutation.
Details
Originalsprache | Englisch |
---|---|
Titel | Fundamentals of Computation Theory - 24th International Symposium, FCT 2023, Proceedings |
Redakteure/-innen | Henning Fernau, Klaus Jansen |
Herausgeber (Verlag) | Springer Science and Business Media B.V. |
Seiten | 147-161 |
Seitenumfang | 15 |
ISBN (Print) | 9783031435867 |
Publikationsstatus | Veröffentlicht - 2023 |
Peer-Review-Status | Ja |
Publikationsreihe
Reihe | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Band | 14292 LNCS |
ISSN | 0302-9743 |
Konferenz
Titel | 24th International Symposium on Fundamentals of Computation Theory |
---|---|
Kurztitel | FCT 2023 |
Veranstaltungsnummer | 24 |
Dauer | 18 - 21 September 2023 |
Webseite | |
Ort | Universität Trier |
Stadt | Trier |
Land | Deutschland |
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- Algorithm, Decorated permutation, Le diagrams, Positroid