{"entities":{"Q1116902":{"pageid":1127651,"ns":120,"title":"Item:Q1116902","lastrevid":69681714,"modified":"2026-04-13T08:40:42Z","type":"item","id":"Q1116902","labels":{"en":{"language":"en","value":"An edge elimination test for the Steiner problem in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4089350"}},"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":"Q1116902$7C7A5F37-FAB6-4438-8567-993DA0478255","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ba3c646f06217d9b1287f7d6d6016727049e2ad1","datavalue":{"value":{"text":"An edge elimination test for the Steiner problem in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1116902$FC6919E9-4D97-4320-904B-4A4C8075066F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"511f38fffbb2815d77b7c0b24f1b02686bdbda08","datavalue":{"value":"0665.90093","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116902$AAE09A30-1D5A-423F-AD00-C8C14D601116","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"543456a4822db646341084b321211de2648a519a","datavalue":{"value":"10.1016/0167-6377(89)90005-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116902$E29E6172-A97C-4FA4-9EB7-5A70D4BBD524","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"21c026d8fc1aca70234cb49bb0398a0a34b1eb76","datavalue":{"value":{"entity-type":"item","numeric-id":609824,"id":"Q609824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116902$9007873F-2637-4027-B159-7564D0F595BC","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":"Q1116902$0195AB12-C570-4DBE-8595-37593917BCA6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116902$B9F16D77-9426-41B0-91D9-C1058CC817D7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1116902$00E512C6-1086-46DD-BBE0-11A9B5555BB8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"72a63585b05999a8d384d357a6763b22c214a382","datavalue":{"value":"It is known that before actually solving the Steiner Problem in graphs, reduction tests can considerably reduce the problem size. One of them, the Least Cost test, eliminates an edge (i,j) if its length exceeds the shortest path length between nodes i and j. This test is considerably improved by replacing shortest path length with `special distance', a notion based on a min-max measure. The test also generalizes a reduction method that uses minimum spanning trees. The matrix of special distances can be calculated in the same time complexity order as the matrix of all the shortest path lengths. Computational results on different types of problem graphs show that respectable reduction is attained by the test.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116902$62986B9E-E451-4274-B006-79860EA69043","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116902$FBC95751-38F7-41D8-BAEE-A9A6E409DEBD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0b4fa5b59eb6fe6e43618f9e005f4a49f4390971","datavalue":{"value":"65K05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116902$B54F014C-AE2B-445C-A0B4-B5B6A19CCA88","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3ab6a55793ad81225c1799d4436ff2fe3851f40b","datavalue":{"value":"4089350","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116902$1BD9D9D2-C535-4ABA-B75E-3D4D4CA36B61","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c74996394679f34109c5a3e8f74d7778428a8dc0","datavalue":{"value":"graph reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116902$8F8EF75B-C2BC-4C86-AD6C-BB637A43B91A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e34e4abfdc99bf380f32b47b78af3fe014b6e286","datavalue":{"value":"bottleneck length","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116902$102069DE-282F-447E-BCB8-80568A4E5EA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"03b11593c9fc521f9c08872ccc41ffd70154ef44","datavalue":{"value":"Steiner Problem in graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116902$1C238A75-3B00-4425-B366-4ABCABF0F76A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d5257a42e933a7b59cb42e593413c0e243b0e640","datavalue":{"value":"reduction tests","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116902$22FFF317-A2C6-46EF-B72F-E34C51BAEA9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"983d2fbfdd935f0713a4c3a9f3cdf4901c8c19e9","datavalue":{"value":"Least Cost test","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116902$4335E4E8-524A-4174-8616-52051599EDDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f85e9f2721221f48af2e899508349c71e3faa29f","datavalue":{"value":"shortest path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116902$4BCD07B1-00D8-4269-9764-0C3CC320E90C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ec7545df2b6acf575cdf0a3557c1ce7cc9328c85","datavalue":{"value":"special distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116902$24BF5534-992E-4D70-9E7A-EF042851FBD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"930816699e323987bf987f4de63664e42a9aab61","datavalue":{"value":"minimum spanning trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1116902$F1DA2147-DC5F-44DC-9EEA-815D45C3BB9D","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":"Q1116902$9DBAEC4D-DD15-4DD8-8621-AD8EEBA735A6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f8f33c971dcc84beaeaa20da052a921b24adeda5","datavalue":{"value":"https://doi.org/10.1016/0167-6377(89)90005-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1116902$813C1812-9266-4D4C-B5A7-E68F86F7431C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7300038a4f84ca09647eeef6f6c6cde67789a9cb","datavalue":{"value":"W2004092973","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1116902$0CB82483-8DC9-483D-BA1C-CFE9DF5B5D17","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":"Q1116902$8A56B6D4-09AB-47D4-9B31-85172DBA11EA","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":"Q1116902$E0EE535E-2C36-4B51-B346-F781226AF459","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":"Q1116902$52FEF50B-0C34-4154-B644-D883506FBFFA","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":"Q1116902$A1E38CD1-6025-413D-855A-2D66ADE617FC","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":"Q1116902$BF3C529B-2DD5-4D3F-80E3-C3C61A3297F3","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":"Q1116902$6F93B9FE-8D69-4185-A3A9-8B2087D521B9","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":"Q1116902$DBF67592-42A1-4402-9D9E-D623BBB747D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56cf648411a5f0ff052a98185ee5cbfaca5b8a8b","datavalue":{"value":{"entity-type":"item","numeric-id":5636922,"id":"Q5636922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1116902$C1BD08BE-9FFC-4F99-B543-B54010247785","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":"Q1116902$4608646D-D2C7-4FD1-9AEF-8AAAB93B995A","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":"Q1116902$6ABD1FEF-B891-45AD-9751-954B993C3F97","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0114abfa7e5fbac74e9c06657333d51aaab6fd09","datavalue":{"value":{"entity-type":"item","numeric-id":3826622,"id":"Q3826622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb5bf089421becd1433ca3b75e991ce3bcf7b73b","datavalue":{"value":{"amount":"+0.9200295805931092","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":"Q1116902$5A9F12F1-8F7C-499C-8617-4D48CEFA6E8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2420c03074b02f9db51287ba5f21db2fadb3e41b","datavalue":{"value":{"entity-type":"item","numeric-id":4395322,"id":"Q4395322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04a8e3f56e1f6cffbb0ac69cbe1c942f1a2e0e65","datavalue":{"value":{"amount":"+0.8688216805458069","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":"Q1116902$50ED3770-9BD5-446A-A2E2-9C7BCE5309FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3a43180a0eed8a371ce2f4d6a1eee62c05cfe3cd","datavalue":{"value":{"entity-type":"item","numeric-id":3471884,"id":"Q3471884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46e2ac460edcbe14be1aea258373c5baa9b2622d","datavalue":{"value":{"amount":"+0.8456883430480957","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":"Q1116902$FF2FDC47-B654-4333-939C-1ED6C9E07F15","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":"eb83c2220a804d0fd5cd2bb52f5464193407311c","datavalue":{"value":{"amount":"+0.8245031237602234","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":"Q1116902$E221E851-6CC7-4E92-B52F-BC42CAB887C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f0017b9fea4eb88c34afc22dc99d57919130a95","datavalue":{"value":{"entity-type":"item","numeric-id":876697,"id":"Q876697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a03aac22cfe81ac80f9db897a00d4850db6d0484","datavalue":{"value":{"amount":"+0.8242539167404175","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":"Q1116902$533F2FC2-22C6-4ADB-A063-8A128A4CD5A0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An edge elimination test for the Steiner problem in graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_edge_elimination_test_for_the_Steiner_problem_in_graphs"}}}}}