On the recognition of permuted bottleneck Monge matrices
From MaRDI portal
Publication:1902890
DOI10.1016/0166-218X(94)00019-AzbMath0840.05058MaRDI QIDQ1902890
Bettina Klinz, Rüdiger Rudolf, Gerhard J. Woeginger
Publication date: 4 July 1996
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorics in computer science (68R05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items
On the recognition of permuted bottleneck Monge matrices ⋮ On the role of bottleneck Monge matrices in combinatorial optimization ⋮ Robinsonian matrices: recognition challenges ⋮ Perspectives of Monge properties in optimization ⋮ Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances ⋮ Monge properties, discrete convexity and applications ⋮ The algebraic Monge property and path problems
Cites Work
- A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs
- On the Monge property of matrices
- Monge sequences, antimatroids, and the transportation problem with forbidden arcs
- Recognition of Gilmore-Gomory traveling salesman problem
- Bipartite permutation graphs
- Geometric applications of a matrix-searching algorithm
- An algorithm for the detection and construction of Monge sequences
- Efficiently solvable special cases of bottleneck travelling salesman problems
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Recognition of \(d\)-dimensional Monge arrays
- A Monge property for the \(d\)-dimensional transportation problem
- Permuting matrices to avoid forbidden submatrices
- On the recognition of permuted bottleneck Monge matrices
- A structure theorem for the consecutive 1's property
- Optimal two- and three-stage production schedules with setup times included
- Universal conditions for algebraic travelling salesman problems to be efficiently solvable
- A concise survey of efficiently solvable special cases of the permutation flow-shop problem
- Efficient parallel algorithms for bipartite permutation graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
