{"entities":{"Q1270820":{"pageid":1281570,"ns":120,"title":"Item:Q1270820","lastrevid":68685783,"modified":"2026-04-13T01:25:48Z","type":"item","id":"Q1270820","labels":{"en":{"language":"en","value":"The forwarding diameter of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1218508"}},"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":"Q1270820$B557BFFE-5789-4656-9F86-9A56DAA6C21A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e37481fe4617df7d2c338343f140b5d269b0da0c","datavalue":{"value":{"text":"The forwarding diameter of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1270820$27732DD6-6B3C-4307-9386-19A58AF6387F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"54296e32e84db9c20756722159ff931db2b94f40","datavalue":{"value":"0908.05055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270820$9A1BED09-9B23-467D-9BB0-C998AE713947","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6444dc1cad3176f3fff67e2623976240c599c769","datavalue":{"value":"10.1016/S0166-218X(98)00041-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270820$0EDC808C-42F9-4DBF-A63A-A196D6A2CF6E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9e47d94cb50e8bff7e07db91cf2e29b89383adf9","datavalue":{"value":{"entity-type":"item","numeric-id":1223001,"id":"Q1223001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270820$2BE3D84E-DEDB-4AF8-8266-39467DEB2AF2","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":"Q1270820$1B93FDA8-7A7D-4021-95BC-17C35F30B9DE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d54e0210f32623b7fe1b28b048e86bc18ae9da5c","datavalue":{"value":{"time":"+1998-12-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1270820$30192B16-E250-4B2C-B42A-BB3C8DFD2954","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3395a2cd6863e39784161d0f578415f36fc38e6f","datavalue":{"value":"http://www.elsevier.com/locate/dam","type":"string"},"datatype":"url"},"type":"statement","id":"Q1270820$B1F086B6-D04A-44E0-B562-3B359251CC9F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a9a62b2b9cc89eacdae9b10cd2a92a7f22553adb","datavalue":{"value":"A routing \\(R\\) in a graph \\(G\\) is a set of paths \\(\\{ R_{xy}: x,y \\in V(G)\\), \\(x \\not=y\\}\\) where, for the ordered pair of vertices \\((x,y)\\), \\(R_{xy}\\) is a path from \\(x\\) to \\(y\\). The load \\(\\xi (G,R,x)\\) of a vertex \\(x\\) in the routing \\(R\\) is the number of paths in \\(R\\) for which \\(x\\) is an interior vertex. In an earlier paper of Chung et al., \\(\\xi\\) was used to define a measure called the vertex-forwarding index of \\(G\\). An allied concept is the following: Let \\(\\mu (G,R) = \\max_{x,y \\in V(G)} \\sum _{z \\in V(R_{xy})-\\{ x, y \\} } \\xi (G,R,z)\\). The forwarding diameter of \\(G\\), \\(\\mu (G)\\), is defined as the minimum of \\(\\mu (G,R)\\) over all possible \\(R\\). The authors employ the theory of queuing networks to explain why \\(\\mu\\) is more suitable than \\(\\xi\\) to handle cases where the object is to minimize the maximum message transmission delay. Bounds for this new index are computed for the cycle, the wheel, the hypercube and the de Bruijn graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270820$FB86ECAD-B50B-4A78-B133-4D2ECE4AB991","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270820$97C42C27-0FA4-4419-9950-FC596F2423C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270820$1A27FAFC-E4C1-47A5-BF7E-11F0242571FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e3ec0ebb66ad9a53653ec1e19a7608e786acef46","datavalue":{"value":"90B18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270820$A8985D4D-B089-44E8-999B-6753817D6596","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f1e213dca595c3ea0f55a7f00738aad99c241a73","datavalue":{"value":"1218508","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270820$8DDBFF34-DDFF-4DDF-A397-184E3BC57008","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"877964aaaa45dd6254d341094776706b5644577b","datavalue":{"value":"forwarding diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270820$78B4DFBB-5522-4404-9EB6-693EDCBBD3DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"31eee358979036a6e40f53bab74d6c6b1c6a39d5","datavalue":{"value":"vertex-forwarding index","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270820$44EEF23A-89E7-49F3-AE15-CC0CA905077B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ae6cc52b35d03b83d5162d854c61cf5b039329e","datavalue":{"value":"cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270820$2F9327B1-F623-4AA2-AF51-CF6FE5835719","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"75f113a56dfa87e9ee95d74e9d49057fd46efaeb","datavalue":{"value":"wheel","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270820$A9F0394A-F737-4F53-B191-2CD2B725405E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84b39af02b6294cfc0ac85512f98aea0041760bd","datavalue":{"value":"hypercube","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270820$31158531-7BF0-4A62-91C1-F536BEB5F3A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5486a903d11614b00d306449a6ba3df91c01be08","datavalue":{"value":"de Bruijn graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1270820$501E1570-5D72-4D22-95A7-B0DB5EFC1253","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf8837edd6f8e1022b15c3d0748921656854f53e","datavalue":{"value":{"entity-type":"item","numeric-id":1811077,"id":"Q1811077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270820$B45FCA73-23D1-4045-965F-101CFC781506","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":"Q1270820$0B678F86-E7DD-467D-8F3C-9CDE1079FA9C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4ad3c5fc99f95ef9f4031575f90fc4203e3759c","datavalue":{"value":{"entity-type":"item","numeric-id":3030727,"id":"Q3030727"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270820$42C86028-0DC2-4BFD-B837-81F5DAE36D76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19fcefff0dc2ee13da66b21a1fce3e55004c8140","datavalue":{"value":{"entity-type":"item","numeric-id":3703064,"id":"Q3703064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270820$072A70F9-24AC-48D8-B1DE-D214FF0E5DCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fbbed28b50b3a34ee4432b3a3f533eaf771874a","datavalue":{"value":{"entity-type":"item","numeric-id":1887642,"id":"Q1887642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270820$B4F3A1D0-1245-4A76-B41B-2D71AF7F625C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e4d73cb62470b2aff92286d5a84202119416462","datavalue":{"value":{"entity-type":"item","numeric-id":1199420,"id":"Q1199420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270820$416D671D-36EF-4497-8967-6A7D0A0F427B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9985be6f775453c278df9704db5bc85f49e95fba","datavalue":{"value":{"entity-type":"item","numeric-id":3944001,"id":"Q3944001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270820$C64DD0BD-BFDC-4E12-AF83-EF8DA545C24D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e101c83ed3f1c0e3699b75fb16d4ea38a497c03","datavalue":{"value":{"entity-type":"item","numeric-id":1823868,"id":"Q1823868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1270820$BB0A22B9-47E5-4789-ABA1-A9586F739CF7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7388d84b7c6e7803a204af2f202d7e39e86cca21","datavalue":{"value":"W2077803883","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1270820$894F0BCF-2D7C-40B0-A977-631077AEF596","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c9aaeed2c595789713e2df1c0b844aeb4bd1c44","datavalue":{"value":{"entity-type":"item","numeric-id":2871601,"id":"Q2871601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"862d40d71ad527cf848d0d3f1d2e427e7075c6e6","datavalue":{"value":{"amount":"+0.873660147190094","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":"Q1270820$C6DC9CC8-436F-43DC-B208-561B0FC72404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dabde16beef0dea32ddfd4ee26d193073b42eec9","datavalue":{"value":{"entity-type":"item","numeric-id":4344452,"id":"Q4344452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2dc3968d674636b0dfb060d0948a4118e9d765b8","datavalue":{"value":{"amount":"+0.8717583417892456","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":"Q1270820$21FAB656-9025-49DA-971A-6D982C975169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba37d5d029e02faf961e65ac3b9b1b3682d9b450","datavalue":{"value":{"entity-type":"item","numeric-id":1923618,"id":"Q1923618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11c983c9fbd9739ba4ce10386e7a9f29e93240ee","datavalue":{"value":{"amount":"+0.8599631786346436","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":"Q1270820$69B29879-4052-4760-A8EB-6FFDE2C0AA6E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The forwarding diameter of graphs","badges":[]}}}}}