{"entities":{"Q1271877":{"pageid":1282627,"ns":120,"title":"Item:Q1271877","lastrevid":70043022,"modified":"2026-04-13T12:03:19Z","type":"item","id":"Q1271877","labels":{"en":{"language":"en","value":"Optimal labellings of rooted directed trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1221608"}},"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":"Q1271877$97CE1D76-58AE-491D-B127-E5146F517A00","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"66767751cf852e95c3c7900a9aa26b0a016759b2","datavalue":{"value":{"text":"Optimal labellings of rooted directed trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1271877$FE0252F7-95B2-4A5F-B676-78C2B8C28BAA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1938a4f8981463c2a184f114285decf3310739c3","datavalue":{"value":"0914.05064","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1271877$76D2128C-51F0-48D1-847F-52F13D84E3AD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9a943872b8aa7453e76cfb05f9af4dd0c97f232e","datavalue":{"value":{"entity-type":"item","numeric-id":1063657,"id":"Q1063657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1271877$E36CF544-9153-43E6-B7D7-DB2E66FE02FB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f171e2d358ed0c5ffcfe728031d35021527481f7","datavalue":{"value":{"entity-type":"item","numeric-id":103557,"id":"Q103557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1271877$8DEF961E-3F67-466A-B138-BE5EB88186C7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6635f9c58864ee18ccf631a94237e7c940ce57fc","datavalue":{"value":{"time":"+1999-06-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1271877$85A68174-6FD7-4CA9-913E-E7FEF9A1053D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a5411ce348fd437dbf2d206317e0fb328103e9ad","datavalue":{"value":"Let \\(D=(V,E)\\) be an uncyclic directed graph with exactly one vertex of outdegree \\(0\\), i.e. \\(D\\) is a rooted directed tree (RDT). The author studies a labelling problem for RDT that arised in scheduling theory. Consider a bijection \\(\\phi:E\\to \\{1,2,\\dots,| E| \\}\\) such that \\(d_{\\phi}(e)=\\phi(v)-\\phi(u)>0\\) for any arc \\((u,v)\\). It can easily be shown that such a bijection always exists. The problem is to find a bijection such that \\(d_{\\phi}(D)=\\sum_{e\\in E} d_{\\phi}(e)\\) is minimum among all feasible bijections. The author proves several necessary, and necessary and sufficient conditions for a bijection to be optimal, and provides an algorithm of complexity \\(O(n^3)\\) for finding an optimal one.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1271877$235B01CA-C5E8-426D-862A-D813CBFEB4E7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1271877$1C7C8149-0D30-4E84-811E-6E71EA624E79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1271877$46BE22C3-41D3-41D0-93D4-85E1628AD728","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f534f5d0ce0fc68cf55e2afa8cb8bc3a0aeb4ff4","datavalue":{"value":"1221608","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1271877$D5C1661B-DAD3-4F09-83BD-25BEC5F7AC37","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49e86ba232df92ddba27da9e4fab3aff969d19e9","datavalue":{"value":"rooted directed tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1271877$EF7FCAF0-5FC0-4761-8CD3-05F736F13D18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87c676c387377645622734e36537a0b0502ceddb","datavalue":{"value":"labelling","type":"string"},"datatype":"string"},"type":"statement","id":"Q1271877$A218D82E-DC32-4555-8FA2-740FF9830A47","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f12e1eb1be75d4426df498c29926dc868c2e1814","datavalue":{"value":{"entity-type":"item","numeric-id":187114,"id":"Q187114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1271877$1B7855E3-45F2-4544-8591-54BE068EAAA6","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":"Q1271877$172C5782-8F4E-4E99-871D-4DAC22AB8C5E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3d9971806653659ef0fd857c69424670f7b588fc","datavalue":{"value":"https://doi.org/10.1006/aama.1998.0579","type":"string"},"datatype":"url"},"type":"statement","id":"Q1271877$7747021C-F756-4403-AA5C-D99F48FF555F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fc30b67c5f0145d180ebf08b4f0e259f8cf9acf1","datavalue":{"value":"W2013365214","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1271877$95BB8846-9717-4A44-BE86-3120382A22A3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0479e2411231996c037adbcede0345cb47efc22","datavalue":{"value":{"entity-type":"item","numeric-id":5567717,"id":"Q5567717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1271877$DF6927B1-39DF-479B-B367-671C68EC8457","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1271877$37860929-9E66-41C3-BD8E-D665838A1BA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b073b70429536ef3ba0b0852f8badb2c326703a","datavalue":{"value":{"entity-type":"item","numeric-id":3998725,"id":"Q3998725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1271877$F573B03D-65B8-46A0-810C-4EF9A7A29741","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a9463ebb7c0d6391b9608becc2d78c55e3361cc3","datavalue":{"value":"10.1006/AAMA.1998.0579","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1271877$A07B7F51-B184-46E0-B5D2-45F396BA5FD9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b62d8738ea4a9f52a4b9bb39dd40ecb8a65ee239","datavalue":{"value":{"entity-type":"item","numeric-id":2062885,"id":"Q2062885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1254004fcf213e63f76bed969f5c4dac77753a9a","datavalue":{"value":{"amount":"+0.77037513256073","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":"Q1271877$00A4054D-F677-4BB9-942B-90ED8394C3CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"af705549db06d5295acbea1e54d7801f69135e52","datavalue":{"value":{"entity-type":"item","numeric-id":5466046,"id":"Q5466046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a0474fa36e4bce739452d750f6b26db9eb45337","datavalue":{"value":{"amount":"+0.7211272716522217","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":"Q1271877$B39B939F-72C4-4D45-9C37-22AD3B540059","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ebf18741cf345d53d693ce3ff6ce098596e4396","datavalue":{"value":{"entity-type":"item","numeric-id":5491762,"id":"Q5491762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5354d49efa9d0faa01e49aaac0e39bcae8ea48c9","datavalue":{"value":{"amount":"+0.7209416031837463","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":"Q1271877$76D78133-A8E0-4AA5-AFA7-808B8D430732","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a384fb87669ebd3e933638d12d54f114f39d0fa","datavalue":{"value":{"entity-type":"item","numeric-id":5251963,"id":"Q5251963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4ec9368bcdb76491be99186554f6ca8f776c19a","datavalue":{"value":{"amount":"+0.7201744318008423","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":"Q1271877$2E3FB0D9-38C5-402B-94A5-AF52932A0772","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Optimal labellings of rooted directed trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Optimal_labellings_of_rooted_directed_trees"}}}}}