{"entities":{"Q1827870":{"pageid":1838612,"ns":120,"title":"Item:Q1827870","lastrevid":69078738,"modified":"2026-04-13T04:32:26Z","type":"item","id":"Q1827870","labels":{"en":{"language":"en","value":"Strong lower bounds for the prize collecting Steiner problem in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2083797"}},"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":"Q1827870$F0DF1FC6-3E04-4161-A6AA-2E34FFBC7F07","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"df432822db19c0df99d913471ac198e6b0a0b5f2","datavalue":{"value":{"text":"Strong lower bounds for the prize collecting Steiner problem in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1827870$5C91B7CB-C866-4973-9DC9-40F52249FA0C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0b23f38f7eebe5486a55f72e3a8d922bc9ce79f9","datavalue":{"value":"1056.90119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1827870$E029C9C5-88E7-4977-B95F-4806E92ECC18","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"42d733c750bfde860b95bab87d3f2ccb4aaeea04","datavalue":{"value":"10.1016/S0166-218X(03)00380-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1827870$6BD29C0C-ED8A-4FA5-B2C5-44DB1EBB0C75","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"62332c262699bb6778b84922830316357338ec07","datavalue":{"value":{"entity-type":"item","numeric-id":247014,"id":"Q247014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$E0EE1C69-B3B4-4464-A399-6AC972430DB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7e26db00f833c42411756239755ac6bad03b61f0","datavalue":{"value":{"entity-type":"item","numeric-id":226720,"id":"Q226720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$144DA2AF-5686-400E-91DF-E8B9E55AA51E","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":"Q1827870$EC3E8F70-9EF5-49C3-9CFA-7505ED56817C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fdf3003d3f6dc4bd36d0ddd91ae69d1d9d4864ff","datavalue":{"value":{"time":"+2004-08-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1827870$0160A07E-C6E8-425C-8EC4-92CF23B7B031","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"35cb8465ca85ba26995d54be2905dc35556d665c","datavalue":{"value":"90C27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1827870$C80B68C8-455D-41AC-8F87-496CC71ECA49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1827870$42CCEF38-B63D-482D-8569-F60F5FD9BD64","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"84d46242f0df5f883071a93dcdd1d25367550b72","datavalue":{"value":"2083797","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1827870$216CAEA5-F369-4AB6-BAD2-C691285DAC2D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2104a937cd3500198c5e7383e00bdc6c6189610f","datavalue":{"value":"Prize collecting Steiner problem in graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1827870$F67C23C1-02C5-4E2B-AF4D-43067AAD0529","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"abffc3c86519bae56603e7bf4b4c00e8e5a83f6b","datavalue":{"value":"Linear programming relaxation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1827870$204CBAF9-9148-45C5-ACDC-619E67D6085D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4384b6baab23c56cffffc6bb5d1bcc67ce7c345","datavalue":{"value":"Lower bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q1827870$E5753D80-8244-413D-A882-58D234B221E0","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"ae5b20a8b24c0e3b45619a24557709ad88cbdc4e","datavalue":{"value":{"entity-type":"item","numeric-id":16337,"id":"Q16337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$51E36728-F872-4880-951F-F0AB15F8416E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"0b253376d87785eee90d90ff07e4c1df77af1160","datavalue":{"value":{"entity-type":"item","numeric-id":16253,"id":"Q16253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$9F99CD08-E7B2-4B78-B687-E792D48A2983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"4d0306a541ac4d64d413698a8167f6dce4fa4ce8","datavalue":{"value":{"entity-type":"item","numeric-id":16269,"id":"Q16269"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$E4736894-6B0E-4649-A322-F867C3B22F0C","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":"Q1827870$0513B017-E0BD-4B17-9F8F-EFF371982E75","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"beafd09c79dfa9f43f527c7e484481f6934843d2","datavalue":{"value":{"entity-type":"item","numeric-id":3056948,"id":"Q3056948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$A45DF3FA-FE03-4B93-91CB-27D29ADB1F7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b534cb0254ac7e53aa86fecf9ad7586d5f0111b1","datavalue":{"value":{"entity-type":"item","numeric-id":3832349,"id":"Q3832349"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$1A4CFA71-F0C3-4391-B0A6-2C51706342EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"12b20ab46315462d71931a68b1b1d3106c7d1f14","datavalue":{"value":{"entity-type":"item","numeric-id":687042,"id":"Q687042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$27B75D9C-FA61-4F38-9074-15375893D315","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"639e3dfdcb46b4d763bde4f04e57e2bd378d52d3","datavalue":{"value":{"entity-type":"item","numeric-id":2747806,"id":"Q2747806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$9B5A2DFD-D3DF-4F58-81D8-1C67CAA889FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fde83dc2358b044be23eaeb3226ac019d5e33e09","datavalue":{"value":{"entity-type":"item","numeric-id":5378639,"id":"Q5378639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$4B80A663-7EA5-4FB8-A3D4-5074350781B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4042a6a8925d33e7ac25ffe3a11c3e8654542cc4","datavalue":{"value":{"entity-type":"item","numeric-id":5668601,"id":"Q5668601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$3C4418A1-F8AC-4339-99DF-46AA476FF95C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46d9c5c5cdeade59a9e0c4401d9c8317d54174b2","datavalue":{"value":{"entity-type":"item","numeric-id":1322552,"id":"Q1322552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$F236873B-D411-4BF7-8701-312B916FF93F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85859d4bf1a3e88a94a43f3e1ce8b0cfd1f2c77b","datavalue":{"value":{"entity-type":"item","numeric-id":3002852,"id":"Q3002852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$587C1EE1-6BE1-47E9-AABE-B23871F621CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf782e57239254752c60a9e2945519e7f4788a8f","datavalue":{"value":{"entity-type":"item","numeric-id":4952698,"id":"Q4952698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$F1610716-8833-4430-B0B3-1248CB7D3AFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e57a56e45f448b1685e752315dc585a00103a8be","datavalue":{"value":{"entity-type":"item","numeric-id":4540078,"id":"Q4540078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$AC4B0264-1031-4A29-8917-02813C00E1B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"088fcd62793540eca8e7e26b182b44e58077359e","datavalue":{"value":{"entity-type":"item","numeric-id":4355916,"id":"Q4355916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$0213C7FB-CEEC-4A95-BDF1-69CF003A86C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ceb283cafe09f5db531d8a59e2d7af6ad87d7bb","datavalue":{"value":{"entity-type":"item","numeric-id":1322553,"id":"Q1322553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$B29FCE51-541B-4924-880F-220A6B7B660A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47220adda183418b2b12d269f0ab3f8bd70ef132","datavalue":{"value":{"entity-type":"item","numeric-id":3674420,"id":"Q3674420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$8C3E660D-9943-4500-84F8-5722DDAD9C07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1a89411279a353372211802e75f51489a21d592","datavalue":{"value":{"entity-type":"item","numeric-id":5679925,"id":"Q5679925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$D092604E-7E5D-4770-A2C0-17FBDD0FACE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d242372ba09b4d0d4cd4aeddcb0eb809fe66c3a","datavalue":{"value":{"entity-type":"item","numeric-id":3789370,"id":"Q3789370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1827870$EEEE8495-5AA4-42F7-BF50-B92B3E2A119F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"280020f857cc1a9ae05af774e88a34f4d9b62cd4","datavalue":{"value":{"entity-type":"item","numeric-id":2741469,"id":"Q2741469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e172d368c291f19be1a2dd4ca6170a7b7c8db51b","datavalue":{"value":{"amount":"+0.9215294122695924","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":"Q1827870$75FABCC0-A4C4-41CE-A936-254745FFF1E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cebe591f09ea865f0ac24ef7593bbffa446a78d0","datavalue":{"value":{"entity-type":"item","numeric-id":1025987,"id":"Q1025987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ca9f1ca4c870ee8ab5aaf833c79265ea948ea245","datavalue":{"value":{"amount":"+0.8552147746086121","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":"Q1827870$594F2BDA-D479-45C6-ACA3-723341E95FF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fca0116c07b783d9fa8e734ccc225873ec64ecfb","datavalue":{"value":{"entity-type":"item","numeric-id":2496025,"id":"Q2496025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"397c7b11656999f03190afbad08af95b08bacea9","datavalue":{"value":{"amount":"+0.8228177428245544","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":"Q1827870$177B24AE-FA67-40EF-A6DD-A21F92760B1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"760cebfe071ee7882de8f83f53b75bcdc317d069","datavalue":{"value":{"entity-type":"item","numeric-id":2583134,"id":"Q2583134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4bf58ea71956e9c728f79a5915b296cbaa5b4d19","datavalue":{"value":{"amount":"+0.8159251809120178","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":"Q1827870$CD674945-80C8-4215-ACF5-661BCE828944","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d3e7669200c8bd1648e7e1be72e4f2747606648","datavalue":{"value":{"entity-type":"item","numeric-id":1952504,"id":"Q1952504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2655bf5bcf71e0973f92c3f1f51ca378ba08566f","datavalue":{"value":{"amount":"+0.8159192204475403","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":"Q1827870$C751ADC2-BE91-4FE5-BBA8-545F935663CA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Strong lower bounds for the prize collecting Steiner problem in graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Strong_lower_bounds_for_the_prize_collecting_Steiner_problem_in_graphs"}}}}}