{"entities":{"Q1582085":{"pageid":1592825,"ns":120,"title":"Item:Q1582085","lastrevid":67919046,"modified":"2026-04-12T20:13:31Z","type":"item","id":"Q1582085","labels":{"en":{"language":"en","value":"Approximation algorithms for the shortest total path length spanning tree problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1512459"}},"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":"Q1582085$BA812B74-5D01-42DE-B5C4-FEA065AA0AD0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f72ec8f02d94bf0bed5c2eabb52b512ef4ea67d1","datavalue":{"value":{"text":"Approximation algorithms for the shortest total path length spanning tree problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1582085$68CA2DCE-1B98-434E-AA96-FA47045585BF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0a2d7cbe5275b9fe0e3fefc9b5dc55e3a35b1e04","datavalue":{"value":"0958.05024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1582085$03B73EA5-3C41-44A5-BF85-075CD5775746","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b7e8c3a7b98a240f8e237901fb243e53a07e275d","datavalue":{"value":"10.1016/S0166-218X(00)00185-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1582085$9F30348B-A361-4D1D-A1E6-5DE9A8EC3ADE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aae4eea64da72d69c82e9f6fb66db118c327710f","datavalue":{"value":{"entity-type":"item","numeric-id":294613,"id":"Q294613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1582085$EF0DB6DC-A0D0-488B-99D9-D25BE19DBFF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ae4baaea64980ca8fbc3cb88c5fb2d37229ccd50","datavalue":{"value":{"entity-type":"item","numeric-id":294614,"id":"Q294614"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1582085$0B020275-CC92-41C0-A98C-71B7E35C9D4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"acb7735f191938e8f63027b7a005242a0024b0e3","datavalue":{"value":{"entity-type":"item","numeric-id":286980,"id":"Q286980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1582085$C195C46E-5DD4-4D60-9C33-41B757AEA93A","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":"Q1582085$298927C3-65CE-4299-9AD2-B0DA98B0E95E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8d02d8cc00f12eca67af7a2b878da9d104452f1b","datavalue":{"value":{"time":"+2001-02-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1582085$D93AC13B-9778-4246-9F02-F044DB25CD7C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"87f5ab5032e6655351c484c740e013f8fdd493c7","datavalue":{"value":"Given an undirected graph with nonnegative weights on the edges, the shortest total path length spanning tree problem is to find a spanning tree minimizing the sum of distances between all pairs of different vertices. This problem is NP-complete. The present paper gives polynomial time approximation algorithms with different time bounds and worst case ratios. Meantime a polynomial time approximation scheme is known; see \\textit{B. Y. Wu. G. Lancia, V. Bafna, K.-M. Chao}, and \\textit{R. Ravi} [SIAM J. Comput. 29, No. 3, 761-778 (2000; Zbl 0941.68159)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1582085$D9BEA105-4783-4B01-BC72-0A911F84B015","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1582085$68363248-F56C-4F40-BB95-BE3178C03BB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1582085$A468336B-9E55-479B-8386-4212B586CFE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1582085$E7F9C07F-AF2F-4CCC-819B-8E83F0FF0B27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1582085$A172F6A4-B609-4A8A-ADBD-B782BCB7908E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"14e1872130e9eec45fbeeff9f022ad9cb965e7a9","datavalue":{"value":"1512459","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1582085$20E845DA-9DCE-4AE0-B02C-C0A7DBB41F50","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1582085$673F7CA2-6F91-4F4E-9136-2983EB6C7638","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1582085$B270C1A3-39C5-44C2-868B-0DE7597C609A","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":"Q1582085$15D2EE9C-7947-4154-97E2-406754CAD879","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b14bc857dd2b4236116e701bbc8cbae934b2c12","datavalue":{"value":{"entity-type":"item","numeric-id":1391132,"id":"Q1391132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1582085$28A9399F-EBE2-491C-9A29-A5A9E108795C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f1e40c2eceabbcb3782d5bd905e54d1c2fa1a4c","datavalue":{"value":{"entity-type":"item","numeric-id":4182675,"id":"Q4182675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1582085$9F7E2511-A789-4317-8746-5BB2BBF3283D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe37a0f894b1bf7483958c501c7f7bc596a095ad","datavalue":{"value":{"entity-type":"item","numeric-id":1902471,"id":"Q1902471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1582085$09A8B034-B03A-409D-A6C6-D0095008DC8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1582085$5C2E41DD-2857-4AAD-979B-E8A9923F50D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2493638b1f48cfa441d8f185fc09f25a954dc5e","datavalue":{"value":{"entity-type":"item","numeric-id":1203038,"id":"Q1203038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1582085$F9FCCED3-520D-40E0-9A2C-3313C1FF459D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"138d808c1a0d7bbfa300ea1020e86219b9fb4bf4","datavalue":{"value":{"entity-type":"item","numeric-id":4229812,"id":"Q4229812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1582085$D9B00FF3-0DD2-49E4-B5F4-D98091421F1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aea5ea7a9985472c080840895d0fc552e3d7cf9f","datavalue":{"value":{"entity-type":"item","numeric-id":3212880,"id":"Q3212880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1582085$A89A58FC-9546-4036-B606-EB61692E41EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfa99331db23e66381b9e84d4b5de6c6b6c83240","datavalue":{"value":{"entity-type":"item","numeric-id":4178943,"id":"Q4178943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1582085$04EB25A5-0539-4ACD-A8C7-BD15CFA3B8E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ad3d85e70f489455e14b0c0a64c34e2bac8046e","datavalue":{"value":{"entity-type":"item","numeric-id":4037677,"id":"Q4037677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1582085$C7FC77DF-A8C8-4F0D-ABE9-29D538B58075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae6723d3a2829547f9d13489ad808e8178ba96fc","datavalue":{"value":{"entity-type":"item","numeric-id":3964299,"id":"Q3964299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1582085$C9200E15-6123-4159-A8F3-537CBC7F8619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d4ea181d23d163386151281f3b292245c0cf485","datavalue":{"value":{"entity-type":"item","numeric-id":4250159,"id":"Q4250159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1582085$19C8EE67-6FF6-4027-A5A1-8CE7D1AD3138","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f38d1df0dc2883016820ab6b679321059fa26735","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(00)00185-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1582085$70E4B022-358F-4357-9BCF-841305452EB6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"215544a44f06b10ea7cd195b123714dbd646ef61","datavalue":{"value":"W2167725364","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1582085$DDBB3DB7-0FCA-4A1C-B809-0A821E632602","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebfac81a1bf8d6ae2c06d888d9a6bd3d68084cc5","datavalue":{"value":{"entity-type":"item","numeric-id":4250159,"id":"Q4250159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab7b0ae66bd6b2ba698c6f11f0ff75c569c6df55","datavalue":{"value":{"amount":"+0.8164690732955933","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":"Q1582085$0A302F5F-BA7F-426C-AF2C-4A3C3A6A27C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66cf843cbfaddf78d5b5719bded0750d0d32cb72","datavalue":{"value":{"entity-type":"item","numeric-id":4500852,"id":"Q4500852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab7b0ae66bd6b2ba698c6f11f0ff75c569c6df55","datavalue":{"value":{"amount":"+0.8164690732955933","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":"Q1582085$17AED4FD-A4F1-4476-9935-729DC5A66884","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50438fd5e395c933f853de95fb4ea557d3d0803c","datavalue":{"value":{"entity-type":"item","numeric-id":4805401,"id":"Q4805401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4cbcc3fe6e552eb566bce6b84aca5b9efb560d0","datavalue":{"value":{"amount":"+0.8162371516227722","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":"Q1582085$B2F1DD24-60EA-4E46-85EC-9C8CC3E78E6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"99c3b31ac1780f8e960f53865379a09578c4a23e","datavalue":{"value":{"entity-type":"item","numeric-id":3140426,"id":"Q3140426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd94e5810277e3446c4befe9b04b4aa9f72e9362","datavalue":{"value":{"amount":"+0.8154034614562988","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":"Q1582085$DDA4C3A4-6E1E-486D-B8DA-0483251DCA0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e8421e39cca40e46aae833c441b13572b75ff41","datavalue":{"value":{"entity-type":"item","numeric-id":4943844,"id":"Q4943844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6594f064892c2dbcd67acc51179572adfd260fb9","datavalue":{"value":{"amount":"+0.8142080903053284","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":"Q1582085$876551AA-FF6A-4AFC-AB1C-FB0E76A816FF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Approximation algorithms for the shortest total path length spanning tree problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Approximation_algorithms_for_the_shortest_total_path_length_spanning_tree_problem"}}}}}