2019/08/30 by Hiroki Furue, Furue, Hiroki, Hiroshi Hirai +1
Computer Science · #68W40 #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1908.11529
openalex publication_date 2019/08/30 · openalex created_date 2019/09/05 · openalex updated_date 2026/07/28
In this paper, we address the weighted linear matroid intersection problem from the computation of the degree of the determinants of a symbolic matrix. We show that a generic algorithm computing the degree of noncommutative determinants, proposed by the second author, becomes an O(mn3 log n) time algorithm for the weighted linear matroid intersection problem, where two matroids are given by column vectors n × m matrices A,B. We reveal that our algorithm is viewed as a "nonstandard" implementation of Frank's weight splitting algorithm for linear matroids. This gives a linear algebraic reasoning to Frank's algorithm. Although our algorithm is slower than existing algorithms in the worst case estimate, it has a notable feature: Contrary to existing algorithms, our algorithm works on different matroids represented by another "sparse" matrices A0,B0, which skips unnecessary Gaussian eliminations for constructing residual graphs.