A new characterization of matrices with the consecutive ones property

DOI10.1016/j.dam.2009.08.001zbMath1227.05101OpenAlexW2091164903MaRDI QIDQ967442

R. Subashini, N. S. Narayanaswamy

Publication date: 28 April 2010

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

Full work available at URL: https://doi.org/10.1016/j.dam.2009.08.001

zbMATH Keywords

interval graphs0-1 matricesconsecutive ones property

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Extremal set theory (05D05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (5)

A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row ⋮ Convex \((0, 1)\)-matrices and their epitopes ⋮ A type of algebraic structure related to sets of intervals ⋮ Obtaining matrices with the consecutive ones property by row deletions ⋮ Polynomial-time local-improvement algorithm for consecutive block minimization

Cites Work

• Unnamed Item
• Unnamed Item
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• On the consecutive ones property
• An extension of a theorem of Fulkerson and Gross
• Incidence matrices and interval graphs
• Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices
• Incidence matrices, interval graphs and seriation in archeology
• A structure theorem for the consecutive 1's property
• A Simple Test for the Consecutive Ones Property

This page was built for publication: A new characterization of matrices with the consecutive ones property