{"entities":{"Q529005":{"pageid":530772,"ns":120,"title":"Item:Q529005","lastrevid":62516118,"modified":"2026-04-11T06:36:51Z","type":"item","id":"Q529005","labels":{"en":{"language":"en","value":"A structural characterization for certifying Robinsonian matrices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6719991"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$4E3BEAAA-1E1A-4E7F-A68E-83646FB5D4C9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fa665e83b8507e8c58595f9b025f38a17c435381","datavalue":{"value":{"text":"A structural characterization for certifying Robinsonian matrices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q529005$2A17F6B0-17C6-41C2-A205-CA62E90110C6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a4d2c38ec17500ba291cc14b390876443727c02c","datavalue":{"value":"1361.05110","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q529005$73D1DC6D-3637-4F58-8B46-7420FA05F0E1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e7df8fff1441ef18744fe1dd7a53aa93a08c6730","datavalue":{"value":{"entity-type":"item","numeric-id":344892,"id":"Q344892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$05E9A81D-AD0E-48D3-8321-6C1FAB7B4281","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"68845d2166c86d596a73ba9c4316b478031ae814","datavalue":{"value":{"entity-type":"item","numeric-id":529003,"id":"Q529003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$BF9E48E8-1AD2-42AD-9252-0554E944BD93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b13125cd9ec0e8ca7493d04b3c5c31be29c414cc","datavalue":{"value":{"entity-type":"item","numeric-id":262308,"id":"Q262308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$930D9B6B-1DBC-4858-B12C-8826BC8415B9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$0DB69D1E-BEF7-480F-A538-A0D18EC784D7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"46a30028c10f94c4944c801c86f2de5dd37da0f3","datavalue":{"value":{"time":"+2017-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q529005$9626A891-AAE7-4EAA-8ACD-AA87F0B61A5C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6f54d3f91f8d6fda219a98af2edfe8a5bf5d875f","datavalue":{"value":"https://arxiv.org/abs/1701.00806","type":"string"},"datatype":"url"},"type":"statement","id":"Q529005$76D56A49-B56C-4A04-B81D-7CDD9ACAA4F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"afef3ee861e0ead8e8f0b9bfbb0997453e37cb1e","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p21","type":"string"},"datatype":"url"},"type":"statement","id":"Q529005$206A5F58-FB80-4BD6-BA37-98B47E32C9AF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a708e14640cd4ae7115ae749d97abfc90a3a4f2f","datavalue":{"value":"Summary: 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.","type":"string"},"datatype":"string"},"type":"statement","id":"Q529005$1FD85DDE-82F0-4FF5-98DC-2D16A0C162E6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q529005$83D58E63-01BE-4283-9AC6-753A4C53863A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"239a4a174af03c82b61364f762873d53ef0a37ef","datavalue":{"value":"05C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q529005$774F38D1-FC7A-41E8-B6BB-7726D630A590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7530ae852489b120b1b979fe5df373da24dc8e97","datavalue":{"value":"91C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q529005$7C8DC516-8DBD-4E6C-904E-8072CCC7F275","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1c2c7608290b04eb60417a4e35caa1f73e6faba5","datavalue":{"value":"15B99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q529005$4FE5D383-F219-4A7F-8C2D-39BB02F8DDD7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q529005$481DECCE-C1CB-49F4-BBFF-169AB186CB63","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9871d1721a0a694f207b5041517a5cd0e28e41ca","datavalue":{"value":"6719991","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q529005$0DC4B93F-D97D-4549-AD12-47EDED6B5889","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0fe623d77c56428bb4fe628a6dde65892ed4cc73","datavalue":{"value":"Robinson ordering","type":"string"},"datatype":"string"},"type":"statement","id":"Q529005$5BB05B87-B09A-46F4-8D9B-457D750571B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2745055f738dc7be490da16ad0c8e010d2e5f539","datavalue":{"value":"Robinson matrix","type":"string"},"datatype":"string"},"type":"statement","id":"Q529005$FDFB941B-80B9-48C9-88A4-3F11AA749327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4845c5a1983400c53e4f909900bab00b964631e6","datavalue":{"value":"seriation","type":"string"},"datatype":"string"},"type":"statement","id":"Q529005$675C1E95-ED1A-46BB-ACDC-F91273644273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"74e3e34ee17bff7c2307e4ea7ef54082a61560ab","datavalue":{"value":"unit interval graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q529005$20718E30-C079-4808-93C4-D6B7E8796652","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee9339b1141db17d90b6638fb1e6651e36e25105","datavalue":{"value":"asteroidal triple","type":"string"},"datatype":"string"},"type":"statement","id":"Q529005$CAAC5BD3-6A91-4A32-86C8-6D29B1C2D1AB","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$0EAC75E6-56B0-4B38-829F-BF72D9F4C89A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a60e6221ef83d49a743481b246e7bc03d57c73a","datavalue":{"value":{"entity-type":"item","numeric-id":5706832,"id":"Q5706832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$6C073F40-67BB-437A-ABA2-763F22E7626F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f962f629616c1a7550c9aa0a1c5eec6883f3dee1","datavalue":{"value":{"entity-type":"item","numeric-id":1378872,"id":"Q1378872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$E0A70DEF-0006-40C0-9BA1-3DC9223ECCB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62fc251f9108edc9f18a84f4adfc8f638279de6f","datavalue":{"value":{"entity-type":"item","numeric-id":1827809,"id":"Q1827809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$6A4E45D9-D393-4AFC-A139-4A7330D46B87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea5da746ecdd07eaaeff3bd5f8333e593374911a","datavalue":{"value":{"entity-type":"item","numeric-id":672408,"id":"Q672408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$79EDCCDF-3ECA-42D9-B647-3C41D5BADFCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef772f6e1f76bbabf157965708eb7681dc17830f","datavalue":{"value":{"entity-type":"item","numeric-id":4250178,"id":"Q4250178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$F58CFFC2-5758-42AF-A04A-863DF6313841","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b733d3c598f4f60dac05c662888fe6ef36a0cf8","datavalue":{"value":{"entity-type":"item","numeric-id":3837390,"id":"Q3837390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$70B92E6D-9C08-474B-8150-F1D63F82DD98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc312dd7f7a48a74852f7187b570dee72946b7d6","datavalue":{"value":{"entity-type":"item","numeric-id":2461218,"id":"Q2461218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$8DF6A779-9C90-4E9F-AB5A-9951511FDD01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6462cc0c0bef572dd85a6892c91fc9e0891a9e4b","datavalue":{"value":{"entity-type":"item","numeric-id":1961461,"id":"Q1961461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$595A2C27-12B4-4B26-9464-EEF379DAED9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fa056a624ac2394928eee38ac6e0143fafd4084","datavalue":{"value":{"entity-type":"item","numeric-id":1853060,"id":"Q1853060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$63BCF644-C3DC-4B0F-8E4D-00AC6BD27648","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a86d62227bc18337e5d84d631c65ab1cc677a81","datavalue":{"value":{"entity-type":"item","numeric-id":2723176,"id":"Q2723176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$AB39A764-5961-4FFE-8573-F292A8FA32D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4c22661ef6bd919d2990ad58a4b566b53aaa5c2","datavalue":{"value":{"entity-type":"item","numeric-id":2536060,"id":"Q2536060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$B17FFFDC-CF2D-46CF-B9B5-4AFBDA20F48F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f873f917c8fa98059d170f5c05e07be87c6b8ec","datavalue":{"value":{"entity-type":"item","numeric-id":5351862,"id":"Q5351862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$2FF145EE-CC21-474D-9122-A3C83DA2357B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85edc49e2762f78197ca674de99175269ad0218d","datavalue":{"value":{"entity-type":"item","numeric-id":3290351,"id":"Q3290351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$CAE3A8BD-0645-4E19-A3A8-5F4808C267FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a7a6c6b8ed22abfff754835104aaed55a1d4a80","datavalue":{"value":{"entity-type":"item","numeric-id":1140988,"id":"Q1140988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$8BE95A46-51F9-4877-B7F2-4F110B390405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e455951b30fab919ff6ca6ac1faaaa0c4d23e16b","datavalue":{"value":{"entity-type":"item","numeric-id":4969706,"id":"Q4969706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$CB273910-829D-4828-90D1-675A4B0F0938","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e786baa016e3559ab71e68a8c9b0f02660fa89e4","datavalue":{"value":{"entity-type":"item","numeric-id":2365550,"id":"Q2365550"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$7CB8D2BE-C895-44DF-870E-72723142A8FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dbe68f2c952bd532ac8deb2f148a839e49611d3","datavalue":{"value":{"entity-type":"item","numeric-id":3313666,"id":"Q3313666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$8F679A62-DE34-4878-914D-97E0E3850488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2dc747c01e0f7acea864aa0822eb28dfc4b8b1d","datavalue":{"value":{"entity-type":"item","numeric-id":269174,"id":"Q269174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$C3867833-EAC2-432A-ABB6-86204F74D8C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfd444ac2099fb3b5a15da02a0171b8b4a45b7ea","datavalue":{"value":{"entity-type":"item","numeric-id":5588432,"id":"Q5588432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q529005$55FFC7F4-3152-493C-A8A8-49D97188D794","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"defb82c79d5b42ac45cffa98e4df91787ba743c3","datavalue":{"value":"bafkreibstyb7q6uke7f3hqb7coakaxdcvswxh62oxhe5vrnpucy43b4kpm","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q529005$BE7FD3FE-A985-4A74-BF30-A40216EAC68B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"561ebcab42ffe8d337940c8344e65f06cec15a10","datavalue":{"value":{"entity-type":"item","numeric-id":5351862,"id":"Q5351862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b2c7bc67759535626f679c6c0ac3d4176ab4a86","datavalue":{"value":{"amount":"+0.7951949834823608","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q529005$10AAD483-443D-415D-B961-EEBAEAE763EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24b073f6b4ba223312cef3f7debb968e1bb2a57b","datavalue":{"value":{"entity-type":"item","numeric-id":2403299,"id":"Q2403299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68ef47139d3a0ce055a47c7be0ab9ff2ccf13d05","datavalue":{"value":{"amount":"+0.779244065284729","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q529005$D4AA85C9-0265-4945-814F-6FB121E4DAFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d008f1bd1cacc599911f181f46b87caad8dc680","datavalue":{"value":{"entity-type":"item","numeric-id":2174877,"id":"Q2174877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80844e07f18c0ea25edd3374944df0d004bead84","datavalue":{"value":{"amount":"+0.7338743209838867","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q529005$BEFDB252-6946-4C2F-A410-AB7D60A94445","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A structural characterization for certifying Robinsonian matrices","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_structural_characterization_for_certifying_Robinsonian_matrices"}}}}}