Well-Scaling Procedure for Deciding Gammoid Class-Membership of Matroids

2018/07/02 by Albrecht, Immanuel
#05B35 #05C20 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1807.00594

Abstract

We introduce a procedure that solves the decision problem whether a given matroid M is a gammoid. The procedure consists of three pieces: First, we introduce a notion of a valid matroid tableau which captures the current state of knowledge regarding the properties of matroids related to the matroid under consideration. Second, we give a sufficient set of rules that may be used to generate valid matroid tableaux. Third, we introduce a succession of steps that ultimately lead to a decisive tableau starting with any valid tableau. We argue that the decision problem scales well with respect to parallel computation models.

Related

• On the sizes of BDDs and ZDDs representing matroids
• Matroid Secretary for Regular and Decomposable Matroids
• An Efficient Reduction of a Gammoid to a Partition Matroid
• Extension of Simple Algorithms to the Matroid Secretary Problem
• Matroids with nine elements