{"entities":{"Q1179756":{"pageid":1190505,"ns":120,"title":"Item:Q1179756","lastrevid":69837669,"modified":"2026-04-13T10:40:58Z","type":"item","id":"Q1179756","labels":{"en":{"language":"en","value":"An approach for the Steiner problem in directed graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 25308"}},"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":"Q1179756$4BA1D96F-7ABD-4F1F-883A-12F5EEF1E0A4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"174a7a991f8777c582eb5df7ba8b7e42696d9f9a","datavalue":{"value":{"text":"An approach for the Steiner problem in directed graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1179756$4B88C6C0-A9B8-4625-8FBA-9E36019F03B8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bfccf13b1cc4e9f5e3ddcac16a0a08bc7359a54f","datavalue":{"value":"0744.90092","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179756$C0646667-B17B-4B3F-8549-56AE7907ECC7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f6eff64b4a40cf2ede19f3d0e39e21e0d67e7a8f","datavalue":{"value":"10.1007/BF02071983","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179756$DA1EB9EB-6097-4B0A-A2A7-E8BEBE064155","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"dfcb92a6e76e06bc41e5154e841b94f862421161","datavalue":{"value":{"entity-type":"item","numeric-id":1179754,"id":"Q1179754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179756$0C49899B-11F2-46FB-8D23-F65CB45948D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4b382eb2e3a068a862d5096a039ff6b343f2c70","datavalue":{"value":{"entity-type":"item","numeric-id":1096543,"id":"Q1096543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179756$A7D57509-2ECC-4179-A45C-78DF23B4D743","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f7ce56be9c16edf1d104a9ebbc08a137b911c481","datavalue":{"value":{"entity-type":"item","numeric-id":337032,"id":"Q337032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179756$BFB2910A-2364-4840-BAAB-B9DD33991E77","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":"Q1179756$651C5707-924E-41E5-8491-212448AC904F","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":"Q1179756$D580B176-9FF7-460C-8FC9-8AB0CCD63EF3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6dc5837a653f962fbee6d38164757dff350cd4b0","datavalue":{"value":"The authors present a scheme to solve Steiner problems in directed graphs using a heuristic method to obtain upper bounds and the \\(k\\) shortest arborescences algorithm to compute lower bounds. They combine these ideas in an enumerative algorithm. The approach is based on both a ranking algorithm to find lower bounds and an improved version of the Wong algorithm to find upper bounds.   Computational results are presented for both the \\(k\\) shortest arborescences algorithm and the heuristic method, including reduction tests for the problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179756$B8D5CE72-37A5-4BF6-B44F-E5ABF774DDAD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bee1f7445f48f88ea32c13733d6b7ad82b5d2674","datavalue":{"value":{"entity-type":"item","numeric-id":803176,"id":"Q803176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179756$C5B8D05F-7A4D-4C82-9C31-DADE2D7E1B58","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179756$D9CA3206-25F3-49FB-A03D-09543A71B2A8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5b91e44de98b8b806fc56bf98fe02f1357116a00","datavalue":{"value":"25308","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179756$A95F6BD1-0D23-4478-AE68-3D667360616C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"816681eea21269f3ad56375e4f8d7d873b144eb6","datavalue":{"value":"enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179756$8EED42EA-4D5B-4A5E-9CE2-97E236203EF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179756$8149ED8D-E824-4696-BE28-3EDE5DC65D23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a7bef3f4e982e481b450c26b805d7087b0dbf24f","datavalue":{"value":"Steiner problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179756$E8857496-F739-432E-8215-0AAA2295EB45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8d31c2daef2a80161502378446e0198f17f748d4","datavalue":{"value":"heuristic method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179756$C78174ED-EFF7-4D82-82D2-5BC39427A185","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b054bbd1ef16f604df0f61144322893e5b9a2a9","datavalue":{"value":"upper bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179756$957679E9-9559-4AE0-BBCF-63561F382990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e8747e19f0f498bfeb5976901c285b9f1ff9988","datavalue":{"value":"ranking algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179756$16A5A9CE-E98D-486A-B18A-363B2E3783E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0e0192fb524376f45dfdd3eb1a809bf3cd5a9489","datavalue":{"value":"lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q1179756$EAF75EC5-1412-4CC5-BC7C-8F7E301ACCE6","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":"Q1179756$5416831A-319A-4FD7-9E75-51D4F389829D","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":"Q1179756$1D125388-AA05-4A6B-8AC3-753BAB426740","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":"Q1179756$1D34E9C9-8797-4530-A199-408E6526E408","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5de03010f5c0f3370819ac2adccb32417aabbf57","datavalue":{"value":{"entity-type":"item","numeric-id":3813625,"id":"Q3813625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179756$FCF40A6D-316D-4691-806F-58AD48F389D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d3e3cfcfc5dd09ceb46d46d8e815e084d66a72a","datavalue":{"value":{"entity-type":"item","numeric-id":3875356,"id":"Q3875356"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179756$88F61661-A9D3-4B93-8939-8CA2BF6CF0EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82bd541ac2ee11a1acfe5ba499f6a5dc9bcea833","datavalue":{"value":{"entity-type":"item","numeric-id":1179756,"id":"Q1179756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179756$5DFDB584-1228-409D-8242-BC0388B67592","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96647cb4f75dc0bec40dd79379cb89c08575c0ee","datavalue":{"value":{"entity-type":"item","numeric-id":5202521,"id":"Q5202521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179756$E1EC394C-282C-4983-B775-1F68528F98FE","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":"Q1179756$5E262C5B-80F3-4809-9A01-BF99BFC7CB19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5dbca73794cca4cf13362493a920789d4969a22d","datavalue":{"value":{"entity-type":"item","numeric-id":3760270,"id":"Q3760270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179756$8C06E424-CCE9-41D2-A5F8-9A8B5051739C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7761f5a7d78fdf6a95c7409831365b923fe504b6","datavalue":{"value":{"entity-type":"item","numeric-id":3790913,"id":"Q3790913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179756$42E59940-F274-48A3-8B90-A381720841CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0650311eaf58d9e1d131a542ba976b8f0f792dfc","datavalue":{"value":{"entity-type":"item","numeric-id":3315294,"id":"Q3315294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1179756$0361B57E-46C3-440C-BAAF-83E47856A3E5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d8fa455781af96cd3b2b36c5dacce27a22107086","datavalue":{"value":"https://doi.org/10.1007/bf02071983","type":"string"},"datatype":"url"},"type":"statement","id":"Q1179756$D0F8E48D-6B91-473C-9B0E-37AAB2AD7E7A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ec9e2e107eec4de6bb9ff23bcc3d614775c50602","datavalue":{"value":"W1967379196","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1179756$B351F4B8-0F02-4F33-94FB-4A336681BEAA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d1d594f1a2f38b8501c9ff338bec0438f161943","datavalue":{"value":{"entity-type":"item","numeric-id":5896365,"id":"Q5896365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0c9a8a8dcd834d0c73cc402c6ff95f47ed40bd4","datavalue":{"value":{"amount":"+0.94000274","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179756$91A42E32-79EC-4208-BBCE-FB85194F08F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1eef229de4c723bac20519ea4ed67b652b4f21b","datavalue":{"value":{"entity-type":"item","numeric-id":4939606,"id":"Q4939606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cd0e6f95d70cd39da9783c3ec0e18cb0474ed6a","datavalue":{"value":{"amount":"+0.9399734","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179756$22A480B0-EF2B-4123-8F12-E68137065B41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cc13bc4644c40a0fd7d58d16bc241839251ff668","datavalue":{"value":{"entity-type":"item","numeric-id":4250182,"id":"Q4250182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cd0e6f95d70cd39da9783c3ec0e18cb0474ed6a","datavalue":{"value":{"amount":"+0.9399734","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179756$6D1A7F55-2382-4659-A1C2-5608A31427FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d462eea43490b95d3b3dc7a54cd619dd9992defd","datavalue":{"value":{"entity-type":"item","numeric-id":3637313,"id":"Q3637313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d08e8b3b9d7b6228ee70ef6265dc8ae69630aa25","datavalue":{"value":{"amount":"+0.9343996","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179756$865F91F2-958D-4C94-8BD4-1217392C421C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54a7733932111af13c635a35566165f2f4a5b154","datavalue":{"value":{"entity-type":"item","numeric-id":4207918,"id":"Q4207918"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d0bb98abdd03b01a0a65f19cb9c57b4a36dbdc2","datavalue":{"value":{"amount":"+0.93300456","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179756$1AF67A31-43A7-4E61-A8F5-DC31C6291EC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb4ea369400ffca4a5539144440bd77684471d62","datavalue":{"value":{"entity-type":"item","numeric-id":3785980,"id":"Q3785980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d30b27d7c01477004adfe98201c59f66d0654b2","datavalue":{"value":{"amount":"+0.93161225","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179756$074B0ECB-587C-4AEA-9BF2-E746ECC17CA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db055fb61c7ea8887ebbb93620efef9ae85dbeb2","datavalue":{"value":{"entity-type":"item","numeric-id":1315992,"id":"Q1315992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e7d43ecb7e84927760015fa9c7904b1229e2037","datavalue":{"value":{"amount":"+0.9314433","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179756$2F46621C-1496-41EB-B545-0F43E00B7EFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbbf3179baa675c8edfd746d2fe47a3c65100641","datavalue":{"value":{"entity-type":"item","numeric-id":1918915,"id":"Q1918915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73eba32f25754d43e8cf8d945949bf775c51f29b","datavalue":{"value":{"amount":"+0.9312931","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179756$057615EA-D6A7-4273-8656-A285E73533B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e26f055c17139a47bd6e78afae364bdbea9352a2","datavalue":{"value":{"entity-type":"item","numeric-id":5753759,"id":"Q5753759"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf7551931895062d1eab5d51aae15af3e69a5e25","datavalue":{"value":{"amount":"+0.9280176","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179756$1E9F7692-AEDE-474C-B7BE-2A3B3582FB63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e04332c3da2e621763ce383a39a106edb4146be9","datavalue":{"value":{"entity-type":"item","numeric-id":3813625,"id":"Q3813625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96f34617d21ba89e368478d9b753d63c265d9177","datavalue":{"value":{"amount":"+0.9231858","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1179756$3D408A7E-118D-4AF8-A661-5F6D1D616D3E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An approach for the Steiner problem in directed graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_approach_for_the_Steiner_problem_in_directed_graphs"}}}}}