scientific article
From MaRDI portal
Publication:3891767
zbMath0446.68036MaRDI QIDQ3891767
Publication date: 1979
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorial aspects of matroids and geometric lattices (05B35) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (66)
On the computation of pfaffians ⋮ A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 $$\times $$ 2 Submatrices ⋮ Maximum matchings in planar graphs via Gaussian elimination ⋮ RNC-approximation algorithms for the steiner problem ⋮ Sublinear Estimation of Weighted Matchings in Dynamic Data Streams ⋮ An identity for bipartite matching and symmetric determinant ⋮ New algorithms for linear \(k\)-matroid intersection and matroid \(k\)-parity problems ⋮ A cost-scaling algorithm for computing the degree of determinants ⋮ On rank-critical matrix spaces ⋮ Tripartite-to-bipartite entanglement transformation by stochastic local operations and classical communication and the structure of matrix spaces ⋮ Unnamed Item ⋮ Connections between graphs and matrix spaces ⋮ Polyhedral techniques in combinatorial optimization: matchings and tours ⋮ A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices ⋮ On testing for zero polynomials by a set of points with bounded precision. ⋮ Symmetries in directed Gaussian graphical models ⋮ Deterministic polynomial identity tests for multilinear bounded-read formulae ⋮ A case of depth-3 identity testing, sparse factorization and duality ⋮ Group-theoretic generalisations of vertex and edge connectivities ⋮ Unnamed Item ⋮ Combinatorial and computational aspects of graph packing and graph decomposition ⋮ Cardinality constrained minimum cut problems: complexity and algorithms. ⋮ Subspace Arrangements, Graph Rigidity and Derandomization Through Submodular Optimization ⋮ MAX-plus objects to study the complexity of graphs ⋮ Many Visits TSP Revisited ⋮ A Weighted Linear Matroid Parity Algorithm ⋮ Read-once polynomial identity testing ⋮ Enumerating alternating matrix spaces over finite fields with explicit coordinates ⋮ Algebraic Independence and Blackbox Identity Testing ⋮ Random pseudo-polynomial algorithms for some combinatorial programming problems ⋮ Processor efficient parallel matching ⋮ Diverse Pairs of Matchings ⋮ Matching theory -- a sampler: From Dénes König to the present ⋮ Structural results on matching estimation with applications to streaming ⋮ The ideal membership problem and polynomial identity testing ⋮ Depth-4 Identity Testing and Noether’s Normalization Lemma ⋮ Deterministically testing sparse polynomial identities of unbounded degree ⋮ Parallel output-sensitive algorithms for combinatorial and linear algebra problems ⋮ A combinatoric interpretation of dual variables for weighted matching and \(f\)-factors ⋮ Spanning trees of 3-uniform hypergraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces ⋮ Orbit Closures of Linear Algebraic Groups ⋮ An identity for matching and skew-symmetric determinant ⋮ Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties) ⋮ Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-$D$ Occur-$k$ Formulas and Depth-3 Transcendence Degree-$k$ Circuits ⋮ Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs ⋮ Adventures in monotone complexity and TFNP ⋮ Operator scaling: theory and applications ⋮ A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2\times 2\) submatrices ⋮ Unnamed Item ⋮ Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings ⋮ Maximum weight bipartite matching in matrix multiplication time ⋮ From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces ⋮ NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs ⋮ Randomised algorithms ⋮ Bipartite Perfect Matching is in Quasi-NC ⋮ Spectral aspects of symmetric matrix signings ⋮ Improved hitting set for orbit of ROABPs ⋮ A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices ⋮ Algorithms for Weighted Matching Generalizations I: Bipartite Graphs, b-matching, and Unweighted f-factors ⋮ The computational complexity of some problems of linear algebra ⋮ Pfaffian Pairs and Parities: Counting on Linear Matroid Intersection and Parity Problems ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ Generalized Wong sequences and their applications to Edmonds' problems
This page was built for publication:
