{"entities":{"Q688696":{"pageid":690545,"ns":120,"title":"Item:Q688696","lastrevid":47200576,"modified":"2025-12-31T23:57:19Z","type":"item","id":"Q688696","labels":{"en":{"language":"en","value":"Complexity of algorithm and operations on trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 438330"}},"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":"Q688696$C4EEEF93-2A42-40E6-B3EB-39B2D259E4DF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2732a5dd0e26140ab03afd91f32478ca0abaf878","datavalue":{"value":{"text":"Complexity of algorithm and operations on trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q688696$3E7C8DC0-FF06-4C5D-BA13-8EBD99A18C3E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7f94f30fc58b5fec8e8f113f1960b332c73d12a9","datavalue":{"value":"0789.68071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688696$C717B331-4F9E-4523-BBF4-0E10D11DD450","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"93d1ee0253ad8974d877ed8e6fe3ba2f24a2520f","datavalue":{"value":"10.1016/0304-3975(93)90312-H","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688696$AEAAF62D-0989-446B-852B-5597EB841825","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688696$3C0BD390-9460-4C87-B0ED-CC5469F53EC7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"22686110a0b022bcb532bcbf192b2bc2d3de178b","datavalue":{"value":{"time":"+1993-12-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q688696$8EFAD6C6-5B83-46D9-8786-976085C5299A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"619d0b5f0503cd9584a69c54be820ae8fa102fe0","datavalue":{"value":"We consider operations on trees like paths reversal and standard path compression. These operations are used in the algorithm to maintain disjoint sets under union [\\textit{R. E. Tarjan} and \\textit{J. van Leeuwen}, J. Assoc. Comput. Mech. 31, 245-281 (1984; Zbl 0632.68043)]. The path reversal had been used in a recent mutual exclusion algorithm [\\textit{M. Trehel} and \\textit{M. M. Naimi}, Tech. Sci. Inf. 6, 141-150 (1987; Zbl 0618.68037)]. We give exact values for the worst-case of a sequence of these operations performed on an arbitrary initial tree. To obtain these results, we first give upper bounds by applying the potential function method of amortized analysis introduced by \\textit{R. E. Tarjan} [SIAM J. Algebraic Discrete Methods 6, 306-318 (1985; Zbl 0599.68046)]. Then, we show up sequences of operations which costs are exactly the upper proved bounds.","type":"string"},"datatype":"string"},"type":"statement","id":"Q688696$8C2AF649-F177-4A14-B1AB-388279B7064A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688696$D2C07BF0-EC48-49AE-8539-49E1E7E7260D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688696$87D106B1-177F-407C-A529-4D089E941BB1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5deec87fcadba3823eeeee124032209219822d63","datavalue":{"value":"438330","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688696$6952B8DE-12CA-4B06-9E50-A8FB774FD154","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea591823299072809f6b541a6f2f53717036865b","datavalue":{"value":"operations on trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q688696$7014C9B2-56D2-41DB-9C9D-1EC26A391004","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba0b90a98cb19d24f18a4a57f558cd97ac823a73","datavalue":{"value":"paths reversal","type":"string"},"datatype":"string"},"type":"statement","id":"Q688696$AA30802A-DB79-4ED5-AA7F-1CA28212CA7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca6327859a1f7ce6860c6fdd86517933ac67821a","datavalue":{"value":"path compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q688696$345C6D0F-3FBC-4788-9007-B852C2EBEF24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c72a8b3f2a4d4dbc966214e61ce03b251bf218b","datavalue":{"value":"mutual exclusion algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q688696$3127891D-A6FF-4427-BAA3-7FF1E67517C7","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2a4696d6dcbfcf60811ca68933d3fdddf72ccd9b","datavalue":{"value":{"entity-type":"item","numeric-id":161521,"id":"Q161521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688696$D9DFC5AA-E3D5-4DE2-AA9E-F4667EBF7493","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"70ba73d1a972244d16b26792fdce05b2a8fd1c4a","datavalue":{"value":{"entity-type":"item","numeric-id":211913,"id":"Q211913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688696$E9E2B20C-8F8D-40FA-B294-AAE2A32A59C6","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":"Q688696$76863883-181F-469B-B51F-8DE1179B402F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d656ee44a323e749d5c6d4cf3e4b8271c3af114","datavalue":{"value":{"entity-type":"item","numeric-id":2542990,"id":"Q2542990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688696$D8DFCA40-FCBA-430C-9661-9D91325A267F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f50bb2463f68a38c17b8200f5931261dc0c5e7e","datavalue":{"value":{"entity-type":"item","numeric-id":4132283,"id":"Q4132283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688696$C9844E15-7F08-4EDF-A011-5E9DEFA25F17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6ccc1521c4f49974c12e2b96437b7393fa1efe3","datavalue":{"value":{"entity-type":"item","numeric-id":4999430,"id":"Q4999430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688696$F5FC68B5-B34F-4498-8126-1C19D0FD45C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3f8f0b4240ad43b4400a2b1a7057f13444b1e8a","datavalue":{"value":{"entity-type":"item","numeric-id":5337563,"id":"Q5337563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688696$E117E9B4-1E14-40D5-B0B6-2155A31A35E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9481f3c59630f3fd0b053d4bbfc80a1f8f7cec27","datavalue":{"value":{"entity-type":"item","numeric-id":1822942,"id":"Q1822942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688696$1B822EF4-DC67-42B9-A603-B3C1D47C84A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5c1bd05985a92c3127ca000180540bcf9a347bd","datavalue":{"value":{"entity-type":"item","numeric-id":688696,"id":"Q688696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688696$ACA5D18C-20F3-4829-9A35-20322013250D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ead4bbfd8d68f13190adb265255c47346951a3f","datavalue":{"value":{"entity-type":"item","numeric-id":4728243,"id":"Q4728243"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688696$8084F06B-F06D-4A05-A394-517B90A6F477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0f53d9231bc5ff64922d7dd218bb49071786117","datavalue":{"value":{"entity-type":"item","numeric-id":3768416,"id":"Q3768416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688696$866A5FBE-B6E0-4477-91DF-1A5671297BC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00910816ba034b6655b7a47d13d1206cc1d40ae2","datavalue":{"value":{"entity-type":"item","numeric-id":3735083,"id":"Q3735083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688696$F8266D74-5FF7-477E-92C0-C87924B4ACD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e9366c82f8a71633f567b778add8be59a85724d","datavalue":{"value":{"entity-type":"item","numeric-id":3769963,"id":"Q3769963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688696$9D385A4F-2F6D-40CD-A731-D8C909993497","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d42838107dc1621b4753838eaa479577ea592bae","datavalue":{"value":"https://doi.org/10.1016/0304-3975(93)90312-h","type":"string"},"datatype":"url"},"type":"statement","id":"Q688696$702CE8EE-1948-4B88-9506-9875A0BAF8F4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3adf36ddfbca6b16d214421b879cebd3a653d854","datavalue":{"value":"W183199228","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688696$459BC621-7BE6-4969-97DB-0420423BA65C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"033c3b5176c3a85ce95977c0f682d2c7e3c2b546","datavalue":{"value":{"entity-type":"item","numeric-id":1822942,"id":"Q1822942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bf9eba04bab698d6f202483ce32ec185b375bb77","datavalue":{"value":{"amount":"+0.8266093134880066","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":"Q688696$F5EB05C8-04B2-452D-83CC-19D153318534","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc54e3040d97ef7f390f6b24db4d73907903fd0e","datavalue":{"value":{"entity-type":"item","numeric-id":3756517,"id":"Q3756517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a892af4c3699aac50b68b580f5af7010ea4d556","datavalue":{"value":{"amount":"+0.7950944900512695","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":"Q688696$A948FF8A-D5A3-4A6B-9659-C9D18DCB332E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55ced15a0cabd4761fc01853c7c739e8a064f755","datavalue":{"value":{"entity-type":"item","numeric-id":3685219,"id":"Q3685219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50370a6149809bb685da617f7a7417216692f1e7","datavalue":{"value":{"amount":"+0.7950927019119263","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":"Q688696$C823F40A-C2EB-42E4-BDD2-415B6160D7BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22ba791631e10b9f8b8b3295b1d7421e4237fc35","datavalue":{"value":{"entity-type":"item","numeric-id":5317162,"id":"Q5317162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3514a3e4fe388cedd6294d67bc2407fa5b72559b","datavalue":{"value":{"amount":"+0.778670072555542","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":"Q688696$708B26FB-59EA-4A98-9187-F1DE3D9AA865","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32df67f13f7d3dac73d68349f3f66f5dbafca222","datavalue":{"value":{"entity-type":"item","numeric-id":3769963,"id":"Q3769963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"566b09730fbbed30dfff83d294ca021279abd578","datavalue":{"value":{"amount":"+0.7772108912467957","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":"Q688696$0D2089E5-D853-450A-90F6-A46EEB3A0395","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:688696","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:688696"}}}}}