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