Amalgam width of matroids

DOI10.1007/978-3-319-03898-8_23zbMATH Open1406.68043arXiv1304.0299OpenAlexW2964186645MaRDI QIDQ2867089FDOQ2867089

Authors: Lukáš Mach, Tomáš Toufar 

Publication date: 10 December 2013

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1304.0299

Recommendations

• Decomposition width of matroids
• Decomposition width of matroids
• A Parametrized Algorithm for Matroid Branch-Width
• Computing Representations of Matroids of Bounded Branch-Width
• Tutte polynomials computable in polynomial time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of matroids and geometric lattices (05B35)

Cited In (2)

• Decomposition width of matroids
• Decomposition width of matroids

This page was built for publication: Amalgam width of matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2867089)