Computing the Degree of Determinants via Combinatorial Relaxation

DOI10.1137/S0097539791201897zbMath0834.05037OpenAlexW1973133099MaRDI QIDQ4852623

Kazuo Murota

Publication date: 10 March 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539791201897

zbMATH Keywords

algorithmperfect matchingsquare matrixpolynomial matrixskew-symmetricweighted matchingscombinatorial relaxationdegree of determinants

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Determinants, permanents, traces, other special matrix functions (15A15) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (18)

Index Reduction via Unimodular Transformations ⋮ An identity for bipartite matching and symmetric determinant ⋮ Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form ⋮ Finding optimal minors of valuated bimatroids ⋮ A cost-scaling algorithm for computing the degree of determinants ⋮ Two algorithms for valuated \(\Delta\)-matroids ⋮ Computing the maximum degree of minors in mixed polynomial matrices via combinatorial relaxation ⋮ On a weighted linear matroid intersection algorithm by deg-det computation ⋮ A Weighted Linear Matroid Parity Algorithm ⋮ Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation ⋮ Combinatorial relaxation algorithm for the entire sequence of the maximum degree of minors ⋮ The generic canonical form of a regular structured matrix pencil ⋮ An identity for matching and skew-symmetric determinant ⋮ Pfaffian pairs and parities: counting on linear matroid intersection and parity problems ⋮ Unnamed Item ⋮ Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings ⋮ Computing valuations of the Dieudonné determinants ⋮ Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems

This page was built for publication: Computing the Degree of Determinants via Combinatorial Relaxation