A structural characterization for certifying Robinsonian matrices
From MaRDI portal
Publication:529005
zbMath1361.05110arXiv1701.00806MaRDI QIDQ529005
Monique Laurent, Matteo Seminaroti, Shin-ichi Tanigawa
Publication date: 18 May 2017
Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1701.00806
Clustering in the social and behavioral sciences (91C20) Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Special matrices (15B99)
Related Items (5)
Cut norm discontinuity of triangular truncation of graphons ⋮ Perfect elimination orderings for symmetric matrices ⋮ Graph sequences sampled from Robinson graphons ⋮ Modules in Robinson Spaces ⋮ The weighted sitting closer to friends than enemies problem in the line
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- An optimal algorithm to recognize Robinsonian dissimilarities
- Simple linear time recognition of unit interval graphs
- The node-deletion problem for hereditary properties is NP-complete
- Recognition of Robinsonian dissimilarities
- A Lex-BFS-based recognition algorithm for Robinsonian matrices
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- A note on the consecutive ones submatrix problem.
- On generating the irredundant conjunctive and disjunctive normal forms of monotone Boolean functions
- Optimal greedy algorithms for indifference graphs
- The Roberts characterization of proper and unit interval graphs
- Incidence matrices, interval graphs and seriation in archeology
- Combinatorial Data Analysis
- Representation of a finite graph by a set of intervals on the real line
- On the Complexity of Dualization of Monotone Disjunctive Normal Forms
- Seriation and matrix reordering methods: An historical overview
- Similarity-First Search: A New Algorithm with Application to Robinsonian Matrix Recognition
This page was built for publication: A structural characterization for certifying Robinsonian matrices
