A good submatrix is hard to find

DOI10.1016/0167-6377(82)90038-4zbMath0506.15012MaRDI QIDQ1836717

John J. III Bartholdi

Publication date: 1982

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(82)90038-4

zbMATH Keywords

identification problem; NP-completeness; hereditary property; monotone property; submatrix; identification of submatrices

Mathematics Subject Classification ID

15B57: Hermitian, skew-Hermitian, and related matrices

90C99: Mathematical programming

Related Items

Optimal Transitions for Targeted Protein Quantification: Best Conditioned Submatrix Selection, An exact approach to the problem of extracting an embedded network matrix, The practical conversion of linear programmes to network flow models, Generalizing the column-row matrix decomposition to multi-way arrays, A network relaxation based enumeration algorithm for set partitioning, Extracting pure network submatrices in linear programs using signed graphs., Quasioptimality of maximum-volume cross interpolation of tensors, The maximum balanced subgraph of a signed graph: applications and solution approaches, Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs, Extracting embedded generalized networks from linear programming problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The node-deletion problem for hereditary properties is NP-complete
• Decomposition of regular matroids
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• Matrix characterizations of circular-arc graphs
• Converting Linear Programs to Network Problems
• Node-Deletion Problems on Bipartite Graphs
• On the complexity of the Maximum Subgraph Problem