{"entities":{"Q2656971":{"pageid":2667714,"ns":120,"title":"Item:Q2656971","lastrevid":57971421,"modified":"2026-04-03T07:13:58Z","type":"item","id":"Q2656971","labels":{"en":{"language":"en","value":"A recognition algorithm for adjusted interval digraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7323975"}},"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":"Q2656971$E2FD892A-9233-4CE2-B381-8CE7285EA85F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"45666ae612562c7a23e69d9c52c8fd04b473ec83","datavalue":{"value":{"text":"A recognition algorithm for adjusted interval digraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2656971$6BCC7828-FDB7-4564-9747-443FD1E66EB3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"456fdedcae72e81cc92a27a0b3bc68e133f57b52","datavalue":{"value":"1506.05202","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2656971$7B5CCCB2-34B4-466E-B5F7-F17DF1F47632","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9c265a071f793084c4e01aa4b1c61508a87915c3","datavalue":{"value":{"entity-type":"item","numeric-id":908311,"id":"Q908311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656971$AB56CD54-9BB3-460E-8B99-E75C84D129B5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656971$AA331E63-1928-4262-B594-308C8E7C2792","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c44e9e40e16b91f474187fb226cbd1d827ea50c7","datavalue":{"value":{"time":"+2021-03-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2656971$6BD426CF-4291-4265-A03C-37A2F3D6A885","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c10bc6f53e7c1597ed72ec080ae4381b64865381","datavalue":{"value":"https://arxiv.org/abs/1810.06162","type":"string"},"datatype":"url"},"type":"statement","id":"Q2656971$BBFC7D95-1596-4EF2-8AF3-F8EEFE1ECACF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fd027b41831bce05266025c7385103e212c2d0f1","datavalue":{"value":"Adjusted interval digraphs, being a generalization of interval graphs, are characterized by the existence of a min ordering and by the absence of invertible pairs. It can be shown that for a given graph with \\(n\\) nodes and \\(m\\) edges, the characterizations of adjusted interval digraphs yield a recognition algorithm with running time \\(O(m^2+n^2)\\), as opposed to a known \\(O(n^4)\\)-time recognition algorithm. The question of finding a linear-time recognition algorithm remains open. The purpose of this paper is to present an \\(O(n^3)\\)-time recognition algorithm for adjusted interval digraphs, thereby producing a min ordering or finding an invertible pair of the given graph if one exists. As a result, it also gives an alternative proof to show that a reflexive digraph has a min ordering if and only if it has no invertible pairs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2656971$BEE16C4C-1483-4AE8-A173-C0913290CD77","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"99fea3d876487c7181e0dff689e3c55a44323330","datavalue":{"value":{"entity-type":"item","numeric-id":592071,"id":"Q592071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656971$8726E084-B023-4239-94C0-35C3A29CE7CF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2656971$DD237252-F3B9-4F85-8BAE-7DED1EFF89A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2656971$48967ABA-5EEE-48EA-8F36-F975369EB7FA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2ea76669d1e2fe1204be00df2f3224cc7b534b55","datavalue":{"value":"7323975","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2656971$DBA8A281-E41F-4244-9D1B-661EB89C9043","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"15e29ee8238bc07899a21a495a38a9c3d5318420","datavalue":{"value":"adjusted interval digraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2656971$5624DF68-5CB7-4C58-A1A2-ED2DC0D727C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"576496d056dcb9700e0b1a36e02b4df78dd995ba","datavalue":{"value":"min ordering","type":"string"},"datatype":"string"},"type":"statement","id":"Q2656971$FA8009D4-49B4-4E23-9D32-0845E094B729","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7decde45aa28f7520212fb84cab816519940f4c9","datavalue":{"value":"recognition algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2656971$9576137E-7B95-4CE9-9271-D02388D91C16","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":"Q2656971$2C2AB4EB-4E29-4130-B923-F18279FA7A7B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5bb8792d6bbdc751ae29f4c37bd72fba64386759","datavalue":{"value":"W3129783352","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2656971$05DFA92D-9D0E-4EDF-9F9B-95F2181BF37D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf035d2fecb7e445991dd16e141f37bab3768a8","datavalue":{"value":{"entity-type":"item","numeric-id":1254112,"id":"Q1254112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656971$217CD94D-34BF-4D62-B48B-4DD8CF579D76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c16ff28efb394beacf6b1fd64453b6a8741f6fca","datavalue":{"value":{"entity-type":"item","numeric-id":415269,"id":"Q415269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656971$034A96F9-8A74-4098-8D09-722463CFD023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67b65643db526bd51a3b8a4e88aab41458af0530","datavalue":{"value":{"entity-type":"item","numeric-id":5130576,"id":"Q5130576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656971$2137225C-24A6-4D3A-A5B5-620AEFBEE08E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d6cd373381835c6f2d57b342c7a1782c31e49f1","datavalue":{"value":{"entity-type":"item","numeric-id":3797238,"id":"Q3797238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656971$AD42F493-F070-4465-83A5-AF5C15726318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76362a000aed78205e15e544e99c407ea95c20b3","datavalue":{"value":{"entity-type":"item","numeric-id":3824435,"id":"Q3824435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656971$67FAB083-0FCE-443D-AD37-854A6ACF5524","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26de6896d18f4127fc3d037092d379679792055a","datavalue":{"value":{"entity-type":"item","numeric-id":602682,"id":"Q602682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656971$CE0BD3DE-6CFA-43EB-B59C-D74512314ADD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ff705a30887218d115abb0d5b90dad7db431d592","datavalue":{"value":"10.1016/J.DAM.2021.02.014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2656971$BA39FC7B-3AA2-4BA0-B0A7-8C51F45163B2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1da3d3152fd6a13c74e8b61af4cbeb70d9e6e3ca","datavalue":{"value":{"entity-type":"item","numeric-id":2839215,"id":"Q2839215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0874d20cbcb96d31cbf8e9c7c8c7eabed36eed82","datavalue":{"value":{"amount":"+0.8380992412567139","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":"Q2656971$E6BE995A-2D68-4462-9614-111A6F4D887F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cfb5bd2cbd5bb15ad10aca39058ec96a5720df6","datavalue":{"value":{"entity-type":"item","numeric-id":415269,"id":"Q415269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1da10608aef58c34cdc88fca31dd62d64ad879c","datavalue":{"value":{"amount":"+0.8228309750556946","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":"Q2656971$9D597BFC-7FEB-4CA3-B72B-312DE4BF5FE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31918eaed6bd0c063f32d8fdbb5efa2ec47ae678","datavalue":{"value":{"entity-type":"item","numeric-id":396800,"id":"Q396800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d93be9f3ce47f49cc569acba06c16a32c60a4b77","datavalue":{"value":{"amount":"+0.7980710864067078","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":"Q2656971$1327C378-C9C6-4BC6-8781-B9C8BC7E13C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"625f77f4049628b41ed6d47e2c238871cfa29d4e","datavalue":{"value":{"entity-type":"item","numeric-id":5005172,"id":"Q5005172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02353c5335ddc68c318689cbc8ec3c0bdd633a2a","datavalue":{"value":{"amount":"+0.7696697115898132","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":"Q2656971$29370ABE-9974-45FA-987F-D156FC403B52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84744e0bf481803265fc254ca1f8f5146aa89701","datavalue":{"value":{"entity-type":"item","numeric-id":1377666,"id":"Q1377666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c36edeac7dcb0444d084ec0170b853f9fd09212","datavalue":{"value":{"amount":"+0.7670846581459045","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":"Q2656971$71C4DCB0-8669-4386-AF29-15F8D3C79E86","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2656971","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2656971"}}}}}