Dear colleagues,
the edge exchange method described in Arturo Merino's noon lecture on May 26 seems to be nearly identical with the memoryless algorithm for computing spanning trees that has appeared in D. Avis and K. Fukuda, "Reverse Search for Enumeration," Discrete Applied Mathematics 6 (1996), 21-46 (see also http://cgm.cs.mcgill.ca/~avis/doc/avis/AF96a.pdf and http://cgm.cs.mcgill.ca/~avis/doc/tutorial.html ).
Best regards, Vašek
Quoting Mykhaylo Tyomkyn tyomkyn@kam.mff.cuni.cz:
Dear all,
This is a reminder that we have a noon lecture by Arturo Merino today at 12:20. Please find the talk details below.
Best regards, Misha.
Greedily generating all bases of a matroid by base exchanges Arturo Merino TU Berlin May 26, 2022, 12:20 in S6
Abstract A classical result states that one can generate a spanning tree by repeatedly adding edges such that no cycle is created. More generally, one can compute a base of a matroid in a similar greedy way. We show that one can not only compute one base of a matroid greedily but exhaustively generate them all by a simple base-exchange 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 new spanning tree (i.e., that hasn’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.
In general, for any matroid, we can greedily compute a listing of all its bases matroid such that consecutive bases differ by base exchanges. Furthermore, we can generate these orders using “history-free” iterative algorithms. More specifically, if m is the number of elements in the matroid, we store O(m) bits of data and use O(m) time per base assuming O(1) time independence and coindependence oracles.
During the talk, we will not assume any previous knowledge of matroids and mainly focus on the particular case of spanning trees of graphs.
This is joint work with Torsten Mütze and Aaron Williams.
TCS-l mailing list -- tcs-l@kam.mff.cuni.cz To unsubscribe send an email to tcs-l-leave@kam.mff.cuni.cz