scientific article; zbMATH DE number 4068895
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.
- Algorithms and Data Structures for an Expanded Family of Matroid Intersection Problems
- scientific article; zbMATH DE number 26304
- Efficient algorithms for a family of matroid intersection problems
- A generalization of Edmonds' matching and matroid intersection algorithms
- scientific article; zbMATH DE number 3904606
- Valuated Matroid Intersection II: Algorithms
- scientific article; zbMATH DE number 4089608
- Efficient theoretic and practical algorithms for linear matroid intersection problems
- Exact and approximation algorithms for weighted matroid intersection
- Exact and approximation algorithms for weighted matroid intersection
- A new algorithm for the intersection of a line with the independent set polytope of a matroid
- Note on recognition of matroid systems
- scientific article; zbMATH DE number 3841889 (Why is no real title available?)
- A time expanded matroid algorithm for finding optimal dynamic matroid intersections
- Improved Bounds for Matroid Partition and Intersection Algorithms
- Two algorithms for weighted matroid intersection
- scientific article; zbMATH DE number 26304 (Why is no real title available?)
- scientific article; zbMATH DE number 123444 (Why is no real title available?)
- Algorithmic characterization of bipartite b-matching and matroid intersection
- An iterative algorithm to find maximum spanning sets and minimum linearly independent sets which partition a finite generator
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)