{"entities":{"Q1179753":{"pageid":1190502,"ns":120,"title":"Item:Q1179753","lastrevid":69837651,"modified":"2026-04-13T10:40:58Z","type":"item","id":"Q1179753","labels":{"en":{"language":"en","value":"The multi-weighted Steiner tree problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 25307"}},"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":"Q1179753$ECD5BC67-2832-48F3-85D1-1E8D9B1250BF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b1b4f62d1b738961ad25db566f71a4b92abf516f","datavalue":{"value":{"text":"The multi-weighted Steiner tree problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1179753$E0A90988-E2E5-42E9-AD7C-551CCDED6A8E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"68e8249c2c732fe1bcfe7631c3b48bf7e6588063","datavalue":{"value":"0744.90089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179753$DDCAB5A3-91C7-49AF-8162-DFE4E3073912","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b6adb3533799864bba35ff8e4276894f753e1b9d","datavalue":{"value":"10.1007/BF02071982","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179753$618A582B-D4E2-4205-A7E3-E9323F1CE25F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2a981753343b2f01f33403fe406af396c6839ce8","datavalue":{"value":{"entity-type":"item","numeric-id":759660,"id":"Q759660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$99F624F8-8410-41E6-B40B-73F2CEE6EF50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f3fd501683197210783baa47eb88e812206e7d71","datavalue":{"value":{"entity-type":"item","numeric-id":531431,"id":"Q531431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$0E952AE5-9085-48C7-BE23-479CEDA81BB6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8f57d1123ebbbd10d621b3552a672e7729202712","datavalue":{"value":{"entity-type":"item","numeric-id":59875,"id":"Q59875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$B60DD64F-A453-4385-B40A-3AE49064F742","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70844ffc4666eabac4e20376c648613dbe8620f7","datavalue":{"value":{"time":"+1992-06-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":"Q1179753$D49B3EE9-D687-4B96-AE2D-E245E261D081","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3d399edbe897db7450197cf7d6fe497846c261d6","datavalue":{"value":"A multi-weighted graph is a graph in which each edge \\(e\\) has 2 (\\(k\\), in general) weights, primary weight \\(p(e)\\) and secondary weight \\(s(e)\\) with \\(p(e)\\geq s(e)\\). Let \\(G=(V,E;p,s)\\) be a multi-weighted graph, \\(K\\) be the special node set of \\(V\\), i.e. \\(V\\setminus K\\) the non-special node set. The multi-weighted Steiner tree problem in this multi-weighted graph is the problem of finding a spanning tree \\(T\\) such that the sum of the primary weights of edges in \\(T_ k\\) and the secondary weights of edges in \\(T\\setminus T_ k\\) is minimum, where \\(T_ k\\) is the subtree of \\(T\\) that covers the special node set \\(K\\).   The multi-weighted Steiner tree problem is a generalization of the Steiner tree problem in graphs, and thus it is NP-hard. This paper develops two heuristic algorithms for the multi-weighted Steiner problem: one is based on weight modifications, the other on exchanging edges. Both of them are of time complexity \\(O(| K| n^ 2)\\), where \\(n\\) is the number of nodes in the graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179753$58A00F0D-EF11-4AAA-B5AE-F99FF169A325","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179753$EA9D834F-8357-422F-A0C5-9149599D27E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d550400b67148ac150a943881fbd05e682ea56f5","datavalue":{"value":"90-08","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179753$FB9CD107-8E6D-40EC-B810-B2AA65C71304","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a075736dd24125fb22e78e1f01acbe15d48baf3f","datavalue":{"value":"90C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179753$2EEB8C08-752C-440D-BAAD-E6B967CFF8F1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cacad24093886999804d6e593816f6f383e61330","datavalue":{"value":"25307","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179753$05DDEEE9-FDC3-4FE8-8AE1-63B7CCF41A4A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49d3ec65c3126b26b8e103839c9cc048c95dfc83","datavalue":{"value":"hierarchical network","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179753$938434CC-C3A3-4827-9B08-44BBFC1EB880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ccd77a3d94536b495eb4a63c6898e3b260632964","datavalue":{"value":"multi-weighted graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179753$BBFFAA5F-720A-4E7D-943C-060D06979D9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0a678a1f35f46f87026da41c75e70bdbc1c0773e","datavalue":{"value":"special node set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179753$B3D8A3CB-EE63-497B-945A-241BA23565A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"97f21a24a76fa57116f716955fa0437a52472e76","datavalue":{"value":"multi- weighted Steiner tree problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179753$FC57B4E4-EC83-4B65-A3E8-F0BA280D797A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179753$9413F72F-189B-4897-8806-1B919257BDC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b6fb9ac68bddbfa8d11616ed9b4850fa8757e1bd","datavalue":{"value":"heuristic algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179753$9A4A5196-E97C-4B6B-A132-2782B8E2F9AB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"07239940f627bb41653311a5b39a7820a8be90f7","datavalue":{"value":{"entity-type":"item","numeric-id":199348,"id":"Q199348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$9161DC67-493D-45A5-80B6-A8E8FC7449DA","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":"Q1179753$E6FA31D7-6E7B-4B46-A024-D3BCF1DBF1F4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"36b6fdb1f001b33b0e5b0ce8bb5969d97429a734","datavalue":{"value":{"entity-type":"item","numeric-id":3786299,"id":"Q3786299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$92B791AD-EE35-4F6B-A19D-5C50FD348050","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a876216ee18dd589b7f0d688cbf9f47bb9b24bc2","datavalue":{"value":{"entity-type":"item","numeric-id":5896365,"id":"Q5896365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$B96D9374-0575-4C0E-9299-8D88F5AF7224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"324a374bf7ce8f1f45cd02e2d227320197ce89b6","datavalue":{"value":{"entity-type":"item","numeric-id":1083378,"id":"Q1083378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$35C19797-001E-46F6-8D0E-A3F6DAB38999","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c46f17a2d874b1825da8e5176316d6645e368cf4","datavalue":{"value":{"entity-type":"item","numeric-id":3787806,"id":"Q3787806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$6F522639-6AED-494B-9E0B-6CA8D46226CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb45060c9f83daddff333c12815009ebd1b6be8d","datavalue":{"value":{"entity-type":"item","numeric-id":1121181,"id":"Q1121181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$FBF8CDBC-FAAE-46A5-9E3A-8C879BE3AB3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aff8986a8c4e797821da51fddec058bb53fd3e51","datavalue":{"value":{"entity-type":"item","numeric-id":3826622,"id":"Q3826622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$50E765AD-37F5-48D0-8BDA-B220EE6B78D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cc026456482e46c1e57009269d387068863adb9","datavalue":{"value":{"entity-type":"item","numeric-id":1116902,"id":"Q1116902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$77C91BC5-17B7-4CF9-8E76-936FE6326F90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$E54A1DAE-1728-4818-858A-07FCF045CD9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89a031afe32dfcbf4f8fba11966dba55c1408ae","datavalue":{"value":{"entity-type":"item","numeric-id":4179026,"id":"Q4179026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$50B94C42-465C-478B-9C47-A6A845C6FD8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0a6fa9559301ce050aa6bf99068d2ede5c82fef","datavalue":{"value":{"entity-type":"item","numeric-id":3956857,"id":"Q3956857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$EE41FE03-5AD7-4293-9B6F-3CFF1295A1C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3dcc4318d82c60e62fc117c0c10950118f2ae66","datavalue":{"value":{"entity-type":"item","numeric-id":1145507,"id":"Q1145507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$0E1FAC68-6680-426A-B9C2-F33D90D34790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"79fa2ab32b7be6c27b1bd9cc19db7e855090ffdf","datavalue":{"value":{"entity-type":"item","numeric-id":5903542,"id":"Q5903542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$C93574DD-106C-4D26-BFD0-186E7B15698F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bda2b0464290995358834d524225361fb9c7e7fd","datavalue":{"value":{"entity-type":"item","numeric-id":3874241,"id":"Q3874241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$2014CD7F-FD33-4BA6-83C0-B02452AD5A10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36455e9240b850eaeb12cd1b9addccac4c2ff640","datavalue":{"value":{"entity-type":"item","numeric-id":5903117,"id":"Q5903117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179753$9305A2F8-409F-44C0-A09A-38E69D257778","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7d08445fcaa21f6b09532079dd49c3d02ceeb1c","datavalue":{"value":{"entity-type":"item","numeric-id":3789370,"id":"Q3789370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1408f984f5aa386d1acc39f2b4ff4d15d69e8f8","datavalue":{"value":{"amount":"+0.8512661457061768","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":"Q1179753$39463F67-4088-460E-B0C0-1545CE10B3A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15c99a6fe9dcae49242cb80ba400b7a109ec7d5c","datavalue":{"value":{"entity-type":"item","numeric-id":3338295,"id":"Q3338295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"abef4653426c57f03293cee79f15902a63d8e88e","datavalue":{"value":{"amount":"+0.8320902585983276","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":"Q1179753$E5B1DB67-3789-4AB3-8EDF-862F2C5DEA24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbdea4ce85821bc80f520cb5799cadafbcdee462","datavalue":{"value":{"entity-type":"item","numeric-id":3693291,"id":"Q3693291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5bc290efa69c13885db9111a91571c7db2eec74","datavalue":{"value":{"amount":"+0.8207106590270996","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":"Q1179753$E3C2775D-5B36-4849-9AAD-9F708DEDBC97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3403160810a3db1919982795b6875ab763dfc82c","datavalue":{"value":{"entity-type":"item","numeric-id":4378524,"id":"Q4378524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac2a0400cae3d6d89521098fca7d4f083eca33fd","datavalue":{"value":{"amount":"+0.8168535828590393","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":"Q1179753$1AFE03CE-9D43-488B-88F8-14E8071DE0CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57386afb95d9c2e47917ba5d92d6b228a23a108b","datavalue":{"value":{"entity-type":"item","numeric-id":1861809,"id":"Q1861809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"424ee2fa59fdbde4bd5d22bcf0481644ee2bdf2b","datavalue":{"value":{"amount":"+0.8150041699409485","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":"Q1179753$A1EF3200-218F-455F-A815-F6E267CE644B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The multi-weighted Steiner tree problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_multi-weighted_Steiner_tree_problem"}}}}}