Computing the maximum degree of minors in matrix pencils via combinatorial relaxation
type: Item
instance of: scholarly article
title: Computing the maximum degree of minors in matrix pencils via combinatorial relaxation
zbMATH Open document ID: 1028.65046
author: Satoru Iwata
published in: Algorithmica
publication date: 2003-08-19T00:00:00Z
review text: The author presents an algorithm for computing the maximum degree of a minor of order \(k\) in a matrix pencil. The algorithm solves the weighted bipartite matching problem. If the upper bound is not tight then the algorithm performs the matrix modification of an equivalence transformation with constant matrices.
Mathematics Subject Classification ID: 65F40
Mathematics Subject Classification ID: 15A22
Mathematics Subject Classification ID: 15A15
zbMATH DE Number: 1967771
zbMATH Keywords: combinatorial relaxation
zbMATH Keywords: determinant
zbMATH Keywords: matrix pencil
zbMATH Keywords: strict equivalence transformation.
zbMATH Keywords: maximum degree of a minor
zbMATH Keywords: weighted bipartite matching problem
MaRDI profile type: Publication
full work available at URL: s00453-003-1022-9
OpenAlex ID: W2002297246
DOI: 10.1007/S00453-003-1022-9
Recommended article: Q4252323
Recommended article: Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation
Recommended article: Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation
Recommended article: Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors in mixed polynomial matrices
Recommended article: Primal-Dual Combinatorial Relaxation Algorithms for the Maximum Degree of Subdeterminants
Recommended article: Matrix Relaxations in Combinatorial Optimization
Recommended article: Combinatorics of Column Minimal Indices and Matrix Pencil Completion Problems
Recommended article: On the computation of maximum minors of Hadamard matrices
Recommended article: Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors
Recommended article: Computing the Degree of Determinants via Combinatorial Relaxation
description: scientific article; zbMATH DE number 1967771