Combinatorial analysis (nonnegative matrices, algorithmic problems)
From MaRDI portal
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Combinatorial aspects of block designs (05B05) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graph theory (05Cxx) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
This survey is a continuation of the previous one by the same authors which was devoted to matrix problems, matroids and the theory of choice [Itogi Nauki Tekh., Ser. Teor. Veroyatn. Mat. Stat. Teor. Kibern. 18, 53- 93 (1981; Zbl 0475.05001); J. Sov. Math. 21, 910-937 (1983)]. It is based mainly on papers reviewed in Ref. Zh. Matematika during 1980-83. The sections are as follows: 1. Existence theorems for (0,1)-matrices: configurations in matrices, incidence matrices of block designs (called block-schemes in translation). 2. Extremal problems for (0,1)-matrices: coverings, depth. 3. Classification of (0,1)-matrices and graphs. 4. Matrices with nonnegative elements: Boolean, integral, real matrices; stochastic and doubly stochastic matrices, permanents (mentioning the proofs of van der Waerden's conjecture by Egorychev and Falikman). 5. Algorithms in algebraic problems: multiplication of matrices, complexity of algorithms, the algebraic assignment problem. 6. Selection problems. 7. Characterization of the classes P and NP. 8. Algorithms on graphs: matchings, paths, cycles; spanning trees, cutsets; colouring; verification of properties of graphs. The bibliography contains 248 items - more than 30 of them by authors from the USSR.
Recommendations
Cites work
- 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 combinatorial problem involving graphs and matrices
- A Method for Finding Permanents of 0, 1 Matrices
- A new result on the problem of Zarankiewicz
- A note on upper bounds for the selection problem
- A Permanent Inequality
- A Polynomial Algorithm for Constructing a Large Bipartite Subgraph, with an Application to a Satisfiability 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
- Algorithms for Edge Coloring Bipartite Graphs and Multigraphs
- Algorithms for minimum covering by cliques and maximum clique in claw- free perfect graphs
- An algorithm for algebraic assignment problems
- 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 asymptotic solution of the multidimensional dimer problem
- An Efficient Cycle Vector Space Algorithm for Listing All Cycles of a Planar Graph
- An extension of the Dulmage-Mendelsohn theorem
- An O(log n) algorithm for computing general order-k Fibonacci numbers
- 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 of finding k-path-free dominating sets in graphs
- Complexity Results for Bandwidth Minimization
- 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 a Maximum Independent Set
- Finding a Minimum Circuit in a Graph
- Finding All Spanning Trees of Directed and Undirected Graphs
- Finding Augmented-Set Bases
- 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
- 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?)
- 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
- Node-Deletion NP-Complete Problems
- Nonnegative factorization of positive semidefinite nonnegative matrices
- Notes on Egoritsjev's proof of the van der Waerden conjecture
- NP-complete decision problems for binary quadratics
- NP-completeness of some generalizations of the maximum matching problem
- 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 Edge Coloring Bipartite Graphs
- On Haber's minimum term rank formula
- On recognizing graph properties from adjacency matrices
- On Ryser's maximum term rank formula
- On some sets of permutation matrices
- On some zero configurations associated with the van der Waerden conjecture
- On the \(n\log{n}\) isomorphism technique (preliminary report)
- On the algorithmic complexity of associative algebras
- On the Asymptotic Complexity of Matrix Multiplication
- 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 Diagonal Hypergraph of a Matrix
- 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 Number of Comparisons to Find the Intersection of Two Relations
- On the Van Der Waerden conjecture for matrices of rank two
- 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 0-1 integer programming problem in a finite ring with identity
- 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 Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
- 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 NP-Completeness of Edge-Coloring
- The NP-Completeness of Some Edge-Partition Problems
- THE RELATIONSHIP BETWEEN THE COMPUTATIONAL COMPLEXITIES OF THE LEGITIMATE DECK AND ISOMORPHISM PROBLEMS
- 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)- Combinatorial matrix analysis conference 20-23 May 1987 university of Victoria, Victoria, B.C. Canada
- Combinatorial matrix analysis: An overview
- scientific article; zbMATH DE number 1805713 (Why is no real title available?)
- scientific article; zbMATH DE number 3427360 (Why is no real title available?)
- scientific article; zbMATH DE number 4043856 (Why is no real title available?)
- scientific article; zbMATH DE number 11399 (Why is no real title available?)
- Positive properties of non-negative matrices
- Description of non-endomorphic maximum perfect ciphers with two-valued plaintext alphabet
- A probabilistic algorithm for finding the term rank of non-negative matrices
- scientific article; zbMATH DE number 3285262 (Why is no real title available?)
- Graph theory (algorithmic, algebraic, and metric problems)
- 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)
