Linear algorithms for testing the sign stability of a matrix and for finding Z-maximum matchings in acyclic graphs

DOI10.1007/BF01389968zbMath0348.65032MaRDI QIDQ1234553

Victor Klee, Pauline van den Driessche

Publication date: 1977

Published in: Numerische Mathematik (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/132487

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Eigenvalues, singular values, and eigenvectors (15A18) Numerical methods for initial value problems involving ordinary differential equations (65L05)

Related Items (13)

A dynamic systems perspective on qualitative simulation ⋮ A qualitative analysis of \(\dot x=Ax+b\) ⋮ Totally positive matrices and cyclic polytopes ⋮ Qualitative comparative statics ⋮ Converting triangulations to quadrangulations ⋮ Toric ideals and graph theory to analyze Hopf bifurcations in mass action systems ⋮ Sign properties of Metzler matrices with applications ⋮ Qualitative stability of linear systems ⋮ Stability of linear systems with uncertain parameters ⋮ Nonsingularity criteria for matrices involving combinatorial considerations ⋮ Allow problems concerning spectral properties of sign pattern matrices: a survey ⋮ Sign stability for switched linear systems and its application in flight control ⋮ Qualitative modelling of linear dynamical systems with quantized state measurements

Cites Work

• Unnamed Item
• Unnamed Item
• Ein Verfahren zur Stabilitätsfrage bei Matrizen-Eigenwertproblemen
• On maximal circuits in directed graphs
• A linear algorithm for the domination number of a tree
• TWO THEOREMS IN GRAPH THEORY
• An Algorithm for a Minimum Cover of a Graph
• Maximum Matching and the Rank of a Matrix
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• Signed Digraphs and the Energy Crisis
• When is a Matrix Sign Stable?
• DISCUSSION PAPER: THE QUALITATIVE ANALYSIS OF PARTIALLY SPECIFIED SYSTEMS
• Predator-Prey Patterns
• Paths, Trees, and Flowers
• Qualitative Problems in Matrix Theory
• Depth-First Search and Linear Graph Algorithms
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: Linear algorithms for testing the sign stability of a matrix and for finding Z-maximum matchings in acyclic graphs