An Efficient Computation of the Rank Function of a Positroid
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
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
| Original language | English |
|---|---|
| Title of host publication | Fundamentals of Computation Theory - 24th International Symposium, FCT 2023, Proceedings |
| Editors | Henning Fernau, Klaus Jansen |
| Publisher | Springer Science and Business Media B.V. |
| Pages | 147-161 |
| Number of pages | 15 |
| ISBN (print) | 9783031435867 |
| Publication status | Published - 2023 |
| Peer-reviewed | Yes |
Publication series
| Series | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 14292 LNCS |
| ISSN | 0302-9743 |
Conference
| Title | 24th International Symposium on Fundamentals of Computation Theory |
|---|---|
| Abbreviated title | FCT 2023 |
| Conference number | 24 |
| Duration | 18 - 21 September 2023 |
| Website | |
| Location | Universität Trier |
| City | Trier |
| Country | Germany |
Keywords
ASJC Scopus subject areas
Keywords
- Algorithm, Decorated permutation, Le diagrams, Positroid