A structural characterization for certifying robinsonian matrices

Monique Laurent, M. Seminaroti, Shin-ichi Tanigawa

Research output: Contribution to journalArticleScientificpeer-review

41 Downloads (Pure)

Abstract

A symmetric matrix is Robinsonian if its rows and columns can be simultaneously reordered in such a way that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. The adjacency matrix of a graph is Robinsonian precisely when the graph is a unit interval graph, so that Robinsonian matrices form a matrix analogue of the class of unit interval graphs. Here we provide a structural characterization for Robinsonian matrices in terms of forbidden substructures, extending the notion of asteroidal triples to weighted graphs. This implies the known characterization of unit interval graphs and leads to an efficient algorithm for certifying that a matrix is not Robinsonian.
Original languageEnglish
Article numberP2.21
Pages (from-to)1-22
Number of pages22
JournalThe Electronic Journal of Combinatorics: EJC
Volume24
Issue number2
Publication statusPublished - 5 May 2017

Fingerprint

Interval Graphs
Unit
Adjacency Matrix
Weighted Graph
Substructure
Graph in graph theory
Symmetric matrix
Monotone
Efficient Algorithms
Analogue
Imply

Keywords

  • robinsonian matrix
  • seriation
  • unit interval graph
  • asteroidal triple

Cite this

@article{5ecebfb8804e42678c12b8eccee5b983,
title = "A structural characterization for certifying robinsonian matrices",
abstract = "A symmetric matrix is Robinsonian if its rows and columns can be simultaneously reordered in such a way that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. The adjacency matrix of a graph is Robinsonian precisely when the graph is a unit interval graph, so that Robinsonian matrices form a matrix analogue of the class of unit interval graphs. Here we provide a structural characterization for Robinsonian matrices in terms of forbidden substructures, extending the notion of asteroidal triples to weighted graphs. This implies the known characterization of unit interval graphs and leads to an efficient algorithm for certifying that a matrix is not Robinsonian.",
keywords = "robinsonian matrix, seriation, unit interval graph, asteroidal triple",
author = "Monique Laurent and M. Seminaroti and Shin-ichi Tanigawa",
year = "2017",
month = "5",
day = "5",
language = "English",
volume = "24",
pages = "1--22",
journal = "The Electronic Journal of Combinatorics: EJC",
issn = "1097-1440",
publisher = "Electronic Journal of Combinatorics",
number = "2",

}

A structural characterization for certifying robinsonian matrices. / Laurent, Monique; Seminaroti, M.; Tanigawa, Shin-ichi.

In: The Electronic Journal of Combinatorics: EJC, Vol. 24, No. 2, P2.21, 05.05.2017, p. 1-22.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - A structural characterization for certifying robinsonian matrices

AU - Laurent, Monique

AU - Seminaroti, M.

AU - Tanigawa, Shin-ichi

PY - 2017/5/5

Y1 - 2017/5/5

N2 - A symmetric matrix is Robinsonian if its rows and columns can be simultaneously reordered in such a way that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. The adjacency matrix of a graph is Robinsonian precisely when the graph is a unit interval graph, so that Robinsonian matrices form a matrix analogue of the class of unit interval graphs. Here we provide a structural characterization for Robinsonian matrices in terms of forbidden substructures, extending the notion of asteroidal triples to weighted graphs. This implies the known characterization of unit interval graphs and leads to an efficient algorithm for certifying that a matrix is not Robinsonian.

AB - A symmetric matrix is Robinsonian if its rows and columns can be simultaneously reordered in such a way that entries are monotone nondecreasing in rows and columns when moving toward the diagonal. The adjacency matrix of a graph is Robinsonian precisely when the graph is a unit interval graph, so that Robinsonian matrices form a matrix analogue of the class of unit interval graphs. Here we provide a structural characterization for Robinsonian matrices in terms of forbidden substructures, extending the notion of asteroidal triples to weighted graphs. This implies the known characterization of unit interval graphs and leads to an efficient algorithm for certifying that a matrix is not Robinsonian.

KW - robinsonian matrix

KW - seriation

KW - unit interval graph

KW - asteroidal triple

M3 - Article

VL - 24

SP - 1

EP - 22

JO - The Electronic Journal of Combinatorics: EJC

JF - The Electronic Journal of Combinatorics: EJC

SN - 1097-1440

IS - 2

M1 - P2.21

ER -