2013/04/01 by Lukas Mach, Mach, Lukas, Tomas Toufar +1
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1 #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1304.0299
arXiv admin note: text overlap with arXiv:0904.2785 by other authors
arxiv created 2013/06/10 · arxiv updated 2013/06/11
We introduce a new matroid width parameter based on the operation of matroid amalgamation, which we call amalgam-width. The parameter is linearly related to branch-width on finitely 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.