Matrix sandwich problems

DOI10.1016/S0024-3795(97)10075-1zbMath0932.05058MaRDI QIDQ1307537

Martin Charles Golumbic

Publication date: 13 March 2000

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

zbMATH Keywords

block decompositionsforbidden submatricesFerrers propertymatrix completion problemsmatrix sandwich problems

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

The graph sandwich problem for 1-join composition is NP-complete, On decision and optimization (\(k\),\(l\))-graph sandwich problems, Chordal bipartite completion of colored graphs, The external constraint 4 nonempty part sandwich problem, The sandwich problem for cutsets: clique cutset, \(k\)-star cutset, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Sandwiches missing two ingredients of order four, The graph sandwich problem for \(P_4\)-sparse graphs, Linear-Time Recognition of Probe Interval Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Positive definite completions of partial Hermitian matrices
• Algorithmic aspects of intersection graphs and representation hypergraphs
• Extensions of band matrices with band inverses
• Ferrers digraphs and threshold graphs
• The complexity of reconstructing trees from qualitative characters and subtrees
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Complexity and algorithms for graph and hypergraph sandwich problems
• The real positive definite completion problem for a simple cycle
• On the complexity of DNA physical mapping
• Completions of partial Jordan and Hessenberg matrices
• Determinantal formulae for matrix completions associated with chordal graphs
• Permuting matrices to avoid forbidden submatrices
• Threshold graphs and related topics
• Incidence matrices and interval graphs
• A structure theorem for the consecutive 1's property
• Complexity and algorithms for reasoning about time
• The Euclidian Distance Matrix Completion Problem
• Graph Sandwich Problems
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• The real positive definite completion problem: cycle completability
• Two strikes against perfect phylogeny
• A Characterization of Comparability Graphs and of Interval Graphs