Amalgam Width of Matroids
2013
We introduce a new matroid width parameter based on the operation of matroid amalgamation called amalgam-width. The parameter is linearly related to branch-width on finitely representable matroids, while still allowing algorithmic applications on non-representable matroids (which is not possible for branch-width). In particular, any property expressible in the monadic second order logic can be decided in linear time for matroids with bounded amalgam-width. We also prove that the Tutte polynomial can be computed in polynomial time for matroids with bounded amalgam-width.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
21
References
1
Citations
NaN
KQI