Robinsonian Matrices: Recognition Challenges

D. Fortin ()
Additional contact information
D. Fortin: INRIA

Journal of Classification, 2017, vol. 34, issue 2, No 3, 222 pages

Abstract: Abstract Ultrametric inequality is involved in different operations on (dis)similarity matrices. Its coupling with a compatible ordering leads to nice interpretations in seriation problems. We accurately review the interval graph recognition problem for its tight connection with recognizing a dense Robinsonian dissimilarity (precisely, in the anti-ultrametric case). Since real life matrices are prone to errors or missing entries, we address the sparse case and make progress towards recognizing sparse Robinsonian dissimilarities with lexicographic breadth first search. The ultrametric inequality is considered from the same graph point of view and the intimate connection between cocomparability graph and dense Robinsonian similarity is established. The current trend in recognizing special graph structures is examined in regard to multiple lexicographic search sweeps. Teaching examples illustrate the issues addressed for both dense and sparse symmetric matrices.

Keywords: Robinsonian matrices; Interval graphs; Cocomparability graphs; Lexicographic searches; Partition refinement (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s00357-017-9230-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jclass:v:34:y:2017:i:2:d:10.1007_s00357-017-9230-1

Ordering information: This journal article can be ordered from
http://www.springer. ... hods/journal/357/PS2

DOI: 10.1007/s00357-017-9230-1

Access Statistics for this article

Journal of Classification is currently edited by Douglas Steinley

More articles in Journal of Classification from Springer, The Classification Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().