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