All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F22%3A10450763" target="_blank" >RIV/00216208:11320/22:10450763 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.4230/LIPIcs.FUN.2022.22" target="_blank" >https://doi.org/10.4230/LIPIcs.FUN.2022.22</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.FUN.2022.22" target="_blank" >10.4230/LIPIcs.FUN.2022.22</a>

Jazyk výsledku

angličtina

Název v původním jazyce

All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges

Popis výsledku v původním jazyce

You provide us with a matroid and an initial base. We say that a subset of the bases &quot;belongs to us&quot; if we can visit each one via a sequence of base exchanges starting from the initial base. It is well-known that &quot;All your base are belong to us&quot;. We refine this classic result by showing that it can be done by a simple greedy algorithm. For example, the spanning trees of a graph can be generated by edge exchanges using the following greedy rule: Minimize the larger label of an edge that enters or exits the current spanning tree and which creates a spanning tree that is new (i.e., hasn&apos;t been visited already). Amazingly, this works for any graph, for any labeling of its edges, for any initial spanning tree, and regardless of how you choose the edge with the smaller label in each exchange. Furthermore, by maintaining a small amount of information, we can generate each successive spanning tree without storing the previous trees. In general, for any matroid, we can greedily compute a listing of all its bases matroid such that consecutive bases differ by a base exchange. Our base exchange Gray codes apply a prefix-exchange on a prefix-minor of the matroid, and we can generate these orders using &quot;history-free&quot;iterative algorithms. More specifically, we store O(m) bits of data, and use O(m) time per base assuming O(1) time independence and coindependence oracles. Our work generalizes and extends a number of previous results. For example, the bases of the uniform matroid are combinations, and they belong to us using homogeneous transpositions via an Eades-McKay style order. Similarly, the spanning trees of fan graphs belong to us via face pivot Gray codes, which extends recent results of Cameron, Grubb, and Sawada [Pivot Gray Codes for the Spanning Trees of a Graph ft. the Fan, COCOON 2021].

Název v anglickém jazyce

All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges

Popis výsledku anglicky

You provide us with a matroid and an initial base. We say that a subset of the bases &quot;belongs to us&quot; if we can visit each one via a sequence of base exchanges starting from the initial base. It is well-known that &quot;All your base are belong to us&quot;. We refine this classic result by showing that it can be done by a simple greedy algorithm. For example, the spanning trees of a graph can be generated by edge exchanges using the following greedy rule: Minimize the larger label of an edge that enters or exits the current spanning tree and which creates a spanning tree that is new (i.e., hasn&apos;t been visited already). Amazingly, this works for any graph, for any labeling of its edges, for any initial spanning tree, and regardless of how you choose the edge with the smaller label in each exchange. Furthermore, by maintaining a small amount of information, we can generate each successive spanning tree without storing the previous trees. In general, for any matroid, we can greedily compute a listing of all its bases matroid such that consecutive bases differ by a base exchange. Our base exchange Gray codes apply a prefix-exchange on a prefix-minor of the matroid, and we can generate these orders using &quot;history-free&quot;iterative algorithms. More specifically, we store O(m) bits of data, and use O(m) time per base assuming O(1) time independence and coindependence oracles. Our work generalizes and extends a number of previous results. For example, the bases of the uniform matroid are combinations, and they belong to us using homogeneous transpositions via an Eades-McKay style order. Similarly, the spanning trees of fan graphs belong to us via face pivot Gray codes, which extends recent results of Cameron, Grubb, and Sawada [Pivot Gray Codes for the Spanning Trees of a Graph ft. the Fan, COCOON 2021].

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA22-15272S" target="_blank" >GA22-15272S: Principy kombinatorického generování</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-232-7

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

28

Strana od-do

1-28

Název nakladatele

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Místo vydání

Dagstuhl, Německo

Místo konání akce

Sicily

Datum konání akce

30. 5. 2022

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—