Amalgam width of matroids

DOI10.1007/978-3-319-03898-8_23MaRDI QIDQ2867089zbMATH OpenOpenAlexFDO

Authors Lukáš Mach, Tomáš Toufar

Publication date 10 December 2013

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

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

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)

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.

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

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)