An Efficient Computation of the Rank Function of a Positroid

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Contributors

  • Lamar Chidiac - , FernUniversität in Hagen (Author)
  • Santiago Guzmán-Pro - , Chair of Algebra and Discrete Structures (Author)
  • Winfried Hochstättler - , FernUniversität in Hagen (Author)
  • Anthony Youssef - , Reply S.p.A (Author)

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 languageEnglish
Title of host publicationFundamentals of Computation Theory - 24th International Symposium, FCT 2023, Proceedings
EditorsHenning Fernau, Klaus Jansen
PublisherSpringer Science and Business Media B.V.
Pages147-161
Number of pages15
ISBN (print)9783031435867
Publication statusPublished - 2023
Peer-reviewedYes

Publication series

SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14292 LNCS
ISSN0302-9743

Conference

Title24th International Symposium on Fundamentals of Computation Theory
Abbreviated titleFCT 2023
Conference number24
Duration18 - 21 September 2023
Website
LocationUniversität Trier
CityTrier
CountryGermany

Keywords

Keywords

  • Algorithm, Decorated permutation, Le diagrams, Positroid