scientific article; zbMATH DE number 4068895

From MaRDI portal
Publication:3801569





Let \(M_ 1=(E,{\mathcal I}_ 1)\), \(M_ 2=(E,{\mathcal I}_ 2)\) be two given matroids, with E as their ground set, and \({\mathcal I}_ 1\), \({\mathcal I}_ 2\) their families of independence sets. For a set of nonempty subsets of E: \(E_ 1,E_ 2,...,E_ m=E\), the author gives in this paper an extended version of cardinality matroid intersection algorithm which produces a set \(I^*\in {\mathcal I}_ 1\cap {\mathcal I}_ 2\) such that for any \(I\in {\mathcal I}_ 1\cap {\mathcal I}_ 2\), 1. \(| I\cap E_ 1| \leq | I^*\cap E_ 1|\), 2. if \(| I\cap E_ i| =| I^*\cap E_ i|\) for \(1\leq i\leq k<m\), then \(| I\cap E_{k+1}| =| I^*\cap E_{k+1}|.\) The upper bound of the times for independence testing of this algorithm is \(O(| E| \rho^ 2)\), where \(\rho =\max (\rho_ 1,\rho_ 2)\), \(\rho_ i\) is the rank of \(M_ i\) \((i=1,2)\), and the times for relabeling are not greater than \(O(m+\rho)\). When \(m=1\), the algorithm becomes the original cardinality matroid intersection algorithm, and its degree of complexity remains the same as that of the original one.











This page was built for publication:

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