Combinatorial analysis (nonnegative matrices, algorithmic problems)

DOI10.1007/BF02104831MaRDI QIDQ1060220zbMATH OpenFDO

Authors V. A. Nosov, V. N. Sachkov, V. E. Tarakanov

Publication date 1985

Published in Journal of Soviet Mathematics (Search for Journal in Brave)

zbMATH Keywords

surveygraph algorithmsnonnegative matricesstochastic matrices(0,1)-matricesalgorithmic problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial aspects of block designs (05B05) Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graph theory (05Cxx)

Recommendations

• scientific article; zbMATH DE number 4043856
• scientific article; zbMATH DE number 679384
• Permanents -- a concise survey
• scientific article; zbMATH DE number 1805713
• scientific article; zbMATH DE number 1534821

Cites work

• scientific article; zbMATH DE number 3834171 (Why is no real title available?)
• scientific article; zbMATH DE number 3836054 (Why is no real title available?)
• scientific article; zbMATH DE number 3836238 (Why is no real title available?)
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 3648718 (Why is no real title available?)
• scientific article; zbMATH DE number 3813636 (Why is no real title available?)
• scientific article; zbMATH DE number 4023282 (Why is no real title available?)
• scientific article; zbMATH DE number 3659735 (Why is no real title available?)
• scientific article; zbMATH DE number 3663177 (Why is no real title available?)
• scientific article; zbMATH DE number 3677892 (Why is no real title available?)
• scientific article; zbMATH DE number 3683782 (Why is no real title available?)
• scientific article; zbMATH DE number 3683792 (Why is no real title available?)
• scientific article; zbMATH DE number 3691375 (Why is no real title available?)
• scientific article; zbMATH DE number 3695388 (Why is no real title available?)
• scientific article; zbMATH DE number 3698952 (Why is no real title available?)
• scientific article; zbMATH DE number 3704754 (Why is no real title available?)
• scientific article; zbMATH DE number 3704755 (Why is no real title available?)
• scientific article; zbMATH DE number 3708581 (Why is no real title available?)
• scientific article; zbMATH DE number 3715590 (Why is no real title available?)
• scientific article; zbMATH DE number 3719169 (Why is no real title available?)
• scientific article; zbMATH DE number 3724467 (Why is no real title available?)
• scientific article; zbMATH DE number 3725714 (Why is no real title available?)
• scientific article; zbMATH DE number 3726376 (Why is no real title available?)
• scientific article; zbMATH DE number 3728277 (Why is no real title available?)
• scientific article; zbMATH DE number 3729461 (Why is no real title available?)
• scientific article; zbMATH DE number 3731953 (Why is no real title available?)
• scientific article; zbMATH DE number 3732068 (Why is no real title available?)
• scientific article; zbMATH DE number 3732077 (Why is no real title available?)
• scientific article; zbMATH DE number 3733266 (Why is no real title available?)
• scientific article; zbMATH DE number 3737686 (Why is no real title available?)
• scientific article; zbMATH DE number 3743308 (Why is no real title available?)
• scientific article; zbMATH DE number 3745168 (Why is no real title available?)
• scientific article; zbMATH DE number 3745187 (Why is no real title available?)
• scientific article; zbMATH DE number 3747167 (Why is no real title available?)
• scientific article; zbMATH DE number 3747338 (Why is no real title available?)
• scientific article; zbMATH DE number 3749772 (Why is no real title available?)
• scientific article; zbMATH DE number 3752213 (Why is no real title available?)
• scientific article; zbMATH DE number 3753004 (Why is no real title available?)
• scientific article; zbMATH DE number 3754868 (Why is no real title available?)
• scientific article; zbMATH DE number 3758342 (Why is no real title available?)
• scientific article; zbMATH DE number 3762116 (Why is no real title available?)
• scientific article; zbMATH DE number 3770975 (Why is no real title available?)
• scientific article; zbMATH DE number 3772432 (Why is no real title available?)
• scientific article; zbMATH DE number 3776884 (Why is no real title available?)
• scientific article; zbMATH DE number 3779343 (Why is no real title available?)
• scientific article; zbMATH DE number 3779345 (Why is no real title available?)
• scientific article; zbMATH DE number 3783052 (Why is no real title available?)
• scientific article; zbMATH DE number 3786761 (Why is no real title available?)
• scientific article; zbMATH DE number 3792183 (Why is no real title available?)
• scientific article; zbMATH DE number 3513809 (Why is no real title available?)
• scientific article; zbMATH DE number 3535592 (Why is no real title available?)
• scientific article; zbMATH DE number 3628400 (Why is no real title available?)
• scientific article; zbMATH DE number 3635493 (Why is no real title available?)
• scientific article; zbMATH DE number 3637616 (Why is no real title available?)
• scientific article; zbMATH DE number 3795968 (Why is no real title available?)
• scientific article; zbMATH DE number 3796005 (Why is no real title available?)
• scientific article; zbMATH DE number 3797772 (Why is no real title available?)
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• A Birkhoff Theorem for Doubly Stochastic Matrices with Vector Entries
• A Method for Finding Permanents of 0, 1 Matrices
• A Permanent Inequality
• A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability Problem
• A combinatorial problem involving graphs and matrices
• A new result on the problem of Zarankiewicz
• A note on upper bounds for the selection problem
• A problem in rearrangements of (0,1)-matrices
• A simple algorithm for finding a cycle of length greater than three and without diagonals
• A system of gaps in the exponent set of primitive matrices
• A theorem in combinatorial matrix theory
• Algorithmic Aspects of Vertex Elimination on Directed Graphs
• Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
• Algorithms for edge coloring bipartite graphs
• Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs
• An Algorithm for Finding K Minimum Spanning Trees
• An Algorithm to Enumerate All Cutsets of a Graph in Linear Time per Cutset
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• An Efficient Cycle Vector Space Algorithm for Listing All Cycles of a Planar Graph
• An O(log n) algorithm for computing general order-k Fibonacci numbers
• An algorithm for algebraic assignment problems
• An asymptotic solution of the multidimensional dimer problem
• An extension of the Dulmage-Mendelsohn theorem
• An optimal algorithm for sink-finding
• Approximation Algorithms for Several Graph Augmentation Problems
• Balanced matrices and property (G)
• Baryzentrische Unterraumschnitte des Simplex
• Behavior of the permanent of a special class of doubly stochastic matrices
• Bemerkungen zu einem Isomorphie-Problem für Graphen, die speziellen Matrizen zugeordnet sind
• Bigraphs versus digraphs via matrices
• Bin packing can be solved within 1+epsilon in linear time
• Bounds for eigenvalues of certain stochastic matrices
• Canonical incidence matrices of graphs
• Comment on a computing the k shortest paths in a graph
• Comment verifier l'associativite d'une table de groupe
• Complement total unimodularity
• Complexity Results for Bandwidth Minimization
• Complexity of finding k-path-free dominating sets in graphs
• Computational comparison of two methods for finding the shortest complete cycle or circuit in a graph
• Computing extremal and approximate distances in graphs having unit cost edges
• Concerning the Magnitude of the Entries in a Doubly Stochastic Matrix
• Concerning the minimum of permanents on doubly stochastic circulants
• Concerning the question of monotonicity of the permanent on the doubly stochastic matrices^†
• Deciding Hadamard equivalence of Hadamard matrices
• Decomposition of Nonnegative Group-Monotone Matrices
• Determinants of circulants of prime power order
• Dominating Sets in Chordal Graphs
• Easy and hard bottleneck location problems
• Edge-Deletion Problems
• Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
• Efficient searching using partial ordering
• Equivalence classes of matrices over finite fields
• Extension of Strassen's estimate to the solution of arbitrary systems of linear equations
• Extreme symmetric doubly stochastic matrices
• Fast, Efficient Parallel Algorithms for Some Graph Problems
• Finding All Spanning Trees of Directed and Undirected Graphs
• Finding Augmented-Set Bases
• Finding a Maximum Independent Set
• Finding a Minimum Circuit in a Graph
• Generalized doubly stochastic and permutation matrices over a ring
• Generating all linear transformations
• Golden ratios in a pairs covering problem
• Graph-theoretic parameters concerning domination, independence, and irredundance
• Idempotent Boolean matrices
• Integer generalized inverses of incidence matrices
• Integral and rational completions of combinatorial matrices
• Integral and rational completions of combinatorial matrices. II
• Invariant Sets for Classes of Matrices of Zeros and Ones
• Line digraphs and the Moore-Penrose inverse
• Matrices and set intersections
• Matrices of 0's and 1's with total support
• Matrices of zeros and ones with fixed row and column sum vectors
• Matrices with isomorphic diagonal hypergraphs
• Minimum dominating cycles in outerplanar graphs
• Monotonicity of permanents of certain doubly stochastic circulant matrices
• Monotonicity of permanents of certain doubly stochastic matrices
• More on integral generalised inverses of integral matrics
• NP-complete decision problems for binary quadratics
• NP-completeness of some generalizations of the maximum matching problem
• Node-Deletion NP-Complete Problems
• Nonnegative factorization of positive semidefinite nonnegative matrices
• Notes on Egoritsjev's proof of the van der Waerden conjecture
• On Edge Coloring Bipartite Graphs
• On Haber's minimum term rank formula
• On Ryser's maximum term rank formula
• On a conjecture by D. Z. Dokovic
• On a conjecture of R. F. Scott (1881)
• On a conjecture of Turán
• On a problem suggested by Olga Taussky-Todd
• On diagonal products of doubly stochastic matrices
• On distribution by rank of bases for vector spaces of matrices over a finite field
• On recognizing graph properties from adjacency matrices
• On some sets of permutation matrices
• On some zero configurations associated with the van der Waerden conjecture
• On the Asymptotic Complexity of Matrix Multiplication
• On the Diagonal Hypergraph of a Matrix
• On the Number of Comparisons to Find the Intersection of Two Relations
• On the Van Der Waerden conjecture for matrices of rank two
• On the \(n\log{n}\) isomorphism technique (preliminary report)
• On the algorithmic complexity of associative algebras
• On the complexity of computing bilinear forms with \(\{0,1\}\) constants
• On the complexity of edge labelings for trees
• On the complexity of some coding problems (Corresp.)
• On the inverse M-matrix problem for (0,1)-matrices
• On the matrix equation A^m= J
• On the minimum value of the permanent of a nearly decomposable doubly stochastic matrix
• On the Đoković conjecture for matrices of rank two
• Optimal packing and covering in the plane are NP-complete
• Packing Problems and Hypergraph Theory: A Survey
• Partitioning trees: Matching, domination, and maximum diameter
• Permanental pairs of doubly stochastic matrices. II
• Permanental polytopes of doubly stochastic matrices
• Permutation-matrix groups with positive sum
• Planar Formulae and Their Uses
• Positive Definite Matrices and Catalan Numbers
• Power symmetric stochastic matrices
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Properties of (0,1)-Matrices With Forbidden Configurations
• Properties of (0,1)-matrices with no triangles
• Properties of (0,1)-matrices without certain configurations
• Properties of a Class of (0,1)-Matrices Covering a given Matrix
• Real essentially stochastic matrices: factorizations into special elementary matrices
• Representing matrices
• Row Stochastic Matrices Similar to Doubly Stochastic Matrices
• Selecting the top three elements
• Small diameter interchange graphs of classes of matrices of zeros and ones
• Some NP-Complete Problems Similar to Graph Isomorphism
• Some Properties of Disjoint Sums of Tensors Related to Matrix Multiplication
• Space efficient algorithms for some graph theoretical problems
• THE RELATIONSHIP BETWEEN THE COMPUTATIONAL COMPLEXITIES OF THE LEGITIMATE DECK AND ISOMORPHISM PROBLEMS
• The 0-1 integer programming problem in a finite ring with identity
• The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
• The NP-Completeness of Edge-Coloring
• The NP-Completeness of Some Edge-Partition Problems
• The \(\mathbb{F}_p\) span of the incidence matrix of a finite projective plane
• The class A(R,S) of (0,1)-matrices
• The complexity of designing a network with minimum diameter
• The complexity of finding maximum disjoint paths with length constraints
• The complexity of lexicographic sorting and searching
• The complexity of satisfiability problems
• The complexity of testing whether a graph is a superconcentrator
• The edge Hamiltonian path problem is NP-complete
• The maximum permanent in
• The network flows approach for matrices with given row and column sums
• The node-deletion problem for hereditary properties is NP-complete
• The size of connected hypergraphs with prescribed covering number
• The solution of van der Waerden's problem for permanents
• The van der Waerden conjecture: Two proofs in one year
• Triangular (0,1)-matrices with prescribed row and column sums
• Trilinear aggregating with implicit canceling for a new acceleration of matrix multiplication
• Two-Commodity Flow
• Using euler partitions to edge color bipartite multigraphs

Cited in

(12)

• scientific article; zbMATH DE number 4043856 (Why is no real title available?)
• Combinatorial matrix analysis: An overview
• Combinatorial matrix analysis conference 20-23 May 1987 university of Victoria, Victoria, B.C. Canada
• scientific article; zbMATH DE number 3285262 (Why is no real title available?)
• Positive properties of non-negative matrices
• scientific article; zbMATH DE number 3427360 (Why is no real title available?)
• Graph theory (algorithmic, algebraic, and metric problems)
• A probabilistic algorithm for finding the term rank of non-negative matrices
• scientific article; zbMATH DE number 1805713 (Why is no real title available?)
• scientific article; zbMATH DE number 11399 (Why is no real title available?)
• Description of non-endomorphic maximum perfect ciphers with two-valued plaintext alphabet
• Combinatorial problems related to origin-destination matrices.

This page was built for publication: Combinatorial analysis (nonnegative matrices, algorithmic problems)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1060220)