Multi-Path Matroids
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2004
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910557943103488 |
|---|---|
| author | Bonin, Joseph E. Gimenez, Omer |
| author_facet | Bonin, Joseph E. Gimenez, Omer |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_math_0410425 |
| institution | arXiv |
| publishDate | 2004 |
| record_format | arxiv |
| spellingShingle | Multi-Path Matroids Bonin, Joseph E. Gimenez, Omer Combinatorics 05B35 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. |
| title | Multi-Path Matroids |
| topic | Combinatorics 05B35 |
| url | https://arxiv.org/abs/math/0410425 |