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

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

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

Original language description

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].

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/GA22-15272S" target="_blank" >GA22-15272S: Principles of combinatorial generation</a><br>

Continuities

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

Publication year

2022

Confidentiality

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

Article name in the collection

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-232-7

ISSN

1868-8969

e-ISSN

—

Number of pages

28

Pages from-to

1-28

Publisher name

Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Place of publication

Dagstuhl, Německo

Event location

Sicily

Event date

May 30, 2022

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—