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