An Efficient Computation of the Rank Function of a Positroid

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Beitragende

  • Lamar Chidiac - , FernUniversität in Hagen (Autor:in)
  • Santiago Guzmán-Pro - , Professur für Algebra und Diskrete Strukturen (Autor:in)
  • Winfried Hochstättler - , FernUniversität in Hagen (Autor:in)
  • Anthony Youssef - , Reply S.p.A (Autor:in)

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

OriginalspracheEnglisch
TitelFundamentals of Computation Theory - 24th International Symposium, FCT 2023, Proceedings
Redakteure/-innenHenning Fernau, Klaus Jansen
Herausgeber (Verlag)Springer Science and Business Media B.V.
Seiten147-161
Seitenumfang15
ISBN (Print)9783031435867
PublikationsstatusVeröffentlicht - 2023
Peer-Review-StatusJa

Publikationsreihe

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

Konferenz

Titel24th International Symposium on Fundamentals of Computation Theory
KurztitelFCT 2023
Veranstaltungsnummer24
Dauer18 - 21 September 2023
Webseite
OrtUniversität Trier
StadtTrier
LandDeutschland

Schlagworte

Schlagwörter

  • Algorithm, Decorated permutation, Le diagrams, Positroid