{"entities":{"Q1010611":{"pageid":1012459,"ns":120,"title":"Item:Q1010611","lastrevid":77732237,"modified":"2026-05-06T09:56:51Z","type":"item","id":"Q1010611","labels":{"en":{"language":"en","value":"Developing new locality results for the Pr\u00fcfer code using a remarkable linear-time decoding algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5540833"}},"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":"Q1010611$F0741898-C6A9-4FE7-91BD-F8E78B1E13B2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"60a9be0e14bf13f63a793860b28f409346924638","datavalue":{"value":{"text":"Developing new locality results for the Pr\u00fcfer code using a remarkable linear-time decoding algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010611$8229CDAC-3368-4CC7-A3CA-F183B8FAD655","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5b43f4f5dc3062d4a82fd092b17b42a4617902d7","datavalue":{"value":"1182.94064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010611$B83C3CE6-3C17-4016-97CB-CE2B3E1DDC17","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"efec001afb13e984ef0181c32908470356ecbbf5","datavalue":{"value":{"entity-type":"item","numeric-id":1010610,"id":"Q1010610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010611$AEE0A4AF-AF2B-4463-87DA-E9B98BFB8593","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7c572262204d1f6e22aa562ddadc543c297af62b","datavalue":{"value":{"entity-type":"item","numeric-id":853002,"id":"Q853002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010611$91E87795-5B33-488F-AFD2-49B0192B05B3","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":"Q1010611$D1417804-D8EA-44CA-ABCD-A5F220335B6E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010611$BDFDB613-814F-4B5A-AB04-576338BFC932","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"803748897e947d8d8c39d1adc678216b186bf318","datavalue":{"value":"https://eudml.org/doc/117184","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010611$6D780040-4B89-4463-8979-C7C140253CDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"aa8ab06792f4cdd071bddf1263be13638d4ae2a0","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_14/Abstracts/v14i1r55.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010611$31BC2260-2E8F-4D43-B517-6C6DC88D1D69","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"41e9942a63318365e14fe79ae01a0687b0540b07","datavalue":{"value":"Summary: The Pr\u00fcfer Code is a bijection between the \\(n^{n-2}\\) trees on the vertex set \\([1,n]\\) and the \\(n^{n-2}\\) strings in the set \\([1,n]^{n-2}\\) (known as Pr\u00fcfer strings of order \\(n\\)). Efficient linear-time algorithms for decoding (i.e., converting string to tree) and encoding (i.e., converting tree to string) are well-known. In this paper, we examine an improved decoding algorithm (due to Cho et al.) that scans the elements of the Pr\u00fcfer string in reverse order, rather than in the usual forward direction. We show that the algorithm runs in linear time without requiring additional data strutures or sorting routines, and is an `online' algorithm --- every time a new string element is read, the algorithm can correctly output an additional tree edge without any knowledge of the future composition of the string. This new decoding algorithm allows us to derive results concerning the `locality' properties of the Pr\u00fcfer Code (i.e., the effect of making small changes to a Pr\u00fcfer string on the structure of the corresponding tree). First, we show that mutating the \\(\\mu\\)th element of a Pr\u00fcfer string (of any order) causes at most \\(\\mu + 1\\) edge-changes in the corresponding tree. We also show that randomly mutating the first element of a random Pr\u00fcfer string of order \\(n\\) causes two edge-changes in the corresponding tree with probability \\(2(n-3)/n(n-1)\\), and one edge-change otherwise. Then, based on computer-aided enumerations, we make three conjectures concerning the locality properties of the Pr\u00fcfer Code, including a formula for the probability that a random mutation to the \\(\\mu\\)th element of a random Pr\u00fcfer string of order \\(n\\) causes exactly one edge-change in the corresponding tree. We show that if this formula is correct, then the probability that a random mutation to a random Pr\u00fcfer string of order \\(n\\) causes exactly one edge-change in the corresponding tree is asymptotically equal to one-third, as \\(n\\) tends to infinity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010611$AB4D9321-FF7A-489F-BE19-2A4193361648","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4430c94528f7856126af01b3ac6ccc7f8c77602b","datavalue":{"value":"94B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010611$B2CB2DC6-6231-4BB9-877E-9C7A44E754D6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"112332d0ef494ad3e4834c6e553ace31eee89e0b","datavalue":{"value":"5540833","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010611$37973049-77BC-4366-B5A3-84AE5430B5EA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cf951ce6c42153dd291a0ae64ed189de4d3cef8","datavalue":{"value":"Pr\u00fcfer code","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010611$4E980AE7-D897-4081-9726-FA365DC91F1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dda91016176599239827b77b72927b41dadc507d","datavalue":{"value":"linear time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010611$CBC0904E-69D7-4485-8C8D-808E6987FD18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5c823d5520cbae0851ffaa49a92d96a2f0e260e8","datavalue":{"value":"decoding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010611$40F721B8-9649-4E57-8B29-27F65FB798F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1cc63564cc1471302778796837f40097e003526d","datavalue":{"value":"string to tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010611$61317B17-E8C8-4A7F-B293-D5CB36B8832E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"86858b19e06e7f53cefb9a2372bf5b13d0adff66","datavalue":{"value":"encoding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010611$6F16D3D2-DA4E-4AC2-8AAB-99912955D415","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"644b4beefb85e4e96253265c15c6f37d7d6d3117","datavalue":{"value":"tree to string","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010611$3BE4DEC2-B5ED-4036-B86C-5B3E46D37DA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"019ae529bf31a8858113343542404d4af2dd529d","datavalue":{"value":"decoding algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010611$9D048BC0-5D20-482C-8CBC-35592FE56181","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c2f0b67538d23ce727652757ccb15840eae40a70","datavalue":{"value":"random Pr\u00fcfer stringrandom mutation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010611$CA1CF0B4-F85C-47C7-B639-632212F2107E","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":"Q1010611$7AF82CE1-8342-447C-82B7-1164C90FBE72","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"1504c2924c43eb275dcd027c664d773267213481","datavalue":{"value":"bafkreigjcmarrgihn6rj54lotilkex2ouo4ehljvri4htt4c4gk2b7dpq4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010611$F5E0CA52-E6C5-486B-B942-9CDD7FAF294F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fe99c58276c64afebc697ffe1e8ec314b7a1fd0","datavalue":{"value":{"entity-type":"item","numeric-id":1010914,"id":"Q1010914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a96c56b3b8fe53e460f4c5839fa99d1aec9d313","datavalue":{"value":{"amount":"+0.9219200015068054","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":"Q1010611$CDAD61F4-42CB-4E3D-9D02-30A35313D764","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2cfbc6690f9e11d8466daf5f039ac3d569711220","datavalue":{"value":{"entity-type":"item","numeric-id":4329049,"id":"Q4329049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb93ddc5791554c7d16c68827cd05e869b7f4f4e","datavalue":{"value":{"amount":"+0.7765257954597473","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":"Q1010611$C619FB90-174B-4E0E-8305-D0A9F18026DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2b4e3254f32ebea6b1d62dddcdad2da50023d22","datavalue":{"value":{"entity-type":"item","numeric-id":1969439,"id":"Q1969439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f0c46782c428ea3be7b991f828e5b4cf3106971","datavalue":{"value":{"amount":"+0.7669468522071838","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":"Q1010611$8A5D165B-9872-49E1-811D-4D9E3C8E7234","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8624cd91a9172193412297dbb35e86517ce60ca9","datavalue":{"value":{"entity-type":"item","numeric-id":5901654,"id":"Q5901654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"948cd6e510e3f973daf91a185e2902230c3b56c6","datavalue":{"value":{"amount":"+0.7612672448158264","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":"Q1010611$D0E17842-E45B-46C7-9865-6585C0E4B0FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9285ed340ca0956fb45851398c29daa13047eec1","datavalue":{"value":{"entity-type":"item","numeric-id":5716943,"id":"Q5716943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1ebe9ff74519ab9bbde9bc7dea0957bc14df191","datavalue":{"value":{"amount":"+0.7608903050422668","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":"Q1010611$FE4AF14D-A45B-49B2-9B78-AA6E0EE08BE5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Developing new locality results for the Pr\u00fcfer code using a remarkable linear-time decoding algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Developing_new_locality_results_for_the_Pr%C3%BCfer_code_using_a_remarkable_linear-time_decoding_algorithm"}}}}}