On the consecutive ones property

DOI10.1016/S0166-218X(98)00078-XzbMath0918.05045MaRDI QIDQ1281779

Guilherme P. Telles, Oscar Porto, João Meidanis

Publication date: 19 August 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

treesbinary matrixconsecutive ones property

Mathematics Subject Classification ID

Trees (05C05) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Biochemistry, molecular biology (92C40)

Related Items (25)

Convex Relaxations for Permutation Problems ⋮ Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs ⋮ Set covering with almost consecutive ones property ⋮ A FILTER-BASED ALGORITHM FOR EFFICIENT COMPOSITION OF FINITE-STATE TRANSDUCERS ⋮ On Robinsonian dissimilarities, the consecutive ones property and latent variable models ⋮ Modeling recreational systems using optimization techniques and information technologies ⋮ A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row ⋮ Tractability Results for the Consecutive-Ones Property with Multiplicity ⋮ A REVIEW OF TREE CONVEX SETS TEST ⋮ Consecutive ones property and PQ-trees for multisets: hardness of counting their orderings ⋮ A faster algorithm for finding minimum Tucker submatrices ⋮ Finding maximum edge bicliques in convex bipartite graphs ⋮ Hardness results on the gapped consecutive-ones property problem ⋮ A new characterization of matrices with the consecutive ones property ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ Consecutive block minimization is 1.5-approximable ⋮ The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure ⋮ Treemaps for Directed Acyclic Graphs ⋮ Filters for Efficient Composition of Weighted Finite-State Transducers ⋮ Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results ⋮ Red-blue covering problems and the consecutive ones property ⋮ Minimal Conflicting Sets for the Consecutive Ones Property in Ancestral Genome Reconstruction ⋮ Linear-Time Recognition of Probe Interval Graphs ⋮ A note on the consecutive ones submatrix problem. ⋮ Obtaining matrices with the consecutive ones property by row deletions

Cites Work

• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• Incidence matrices, interval graphs and seriation in archeology
• A structure theorem for the consecutive 1's property
• Achieving optimality for gate matrix layout and PLA folding: a graph theoretic approach
• Algorithmic Aspects of Vertex Elimination on Graphs
• Construction of TernaryH_v-groups and TernaryP-hyperoperations
• File organization

This page was built for publication: On the consecutive ones property