a1 Department of Mathematics, The George Washington University, Washington, DC 20052, USA (e-mail: email@example.com)
a2 Departament de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Jordi Girona 1–3, 08034, Barcelona, Spaine (e-mail: firstname.lastname@example.org)
We introduce the minor-closed, dual-closed class of multi-path matroids. We give a polynomial-time algorithm for computing the Tutte polynomial of a multi-path matroid, we describe their basis activities, and we prove some basic structural properties. Key elements of this work are two complementary perspectives we develop for these matroids: on the one hand, multi-path matroids are transversal matroids that have special types of presentations; on the other hand, the bases of multi-path matroids can be viewed as sets of lattice paths in certain planar diagrams.
(Received October 19 2004)
(Revised December 06 2005)
† Partially supported by Beca Fundació Crèdit Andorrà. Current address: Universitat Pompeu Fabra, Departament de Tecnologia, Passeig de Circunval.lació 8, 08003 Barcelona, Spain.