A tight bound on the length of odd cycles in the incompatibility graph of a non-C1P matrix

DOI10.1016/j.ipl.2012.07.004zbMath1248.68384arXiv1109.0562OpenAlexW2075486215MaRDI QIDQ456131

Tamon Stephen, Mehrnoush Malekesmaeili, Cedric Chauve

Publication date: 23 October 2012

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1109.0562

zbMATH Keywords

graph algorithmsincompatibility graphconsecutive ones propertycertifying algorithmTucker patterns

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Enumerative combinatorics (05A99) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• A structure theorem for the consecutive 1's property
• Unnamed Item
• Unnamed Item

This page was built for publication: A tight bound on the length of odd cycles in the incompatibility graph of a non-C1P matrix