{"entities":{"Q1085182":{"pageid":1095934,"ns":120,"title":"Item:Q1085182","lastrevid":66103929,"modified":"2026-04-12T07:34:36Z","type":"item","id":"Q1085182","labels":{"en":{"language":"en","value":"An optimization problem on graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3981214"}},"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":"Q1085182$C6FFC580-2DAC-4A09-AD7C-132A2A0F1176","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c6f79a65f7ce81a4393f0f4b435958d6eb262280","datavalue":{"value":{"text":"An optimization problem on graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1085182$47A8B90C-A9E2-4268-B64E-94CEBF8EFBA5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"656772535b56a15974b0b2dc779fb97b4bcbb988","datavalue":{"value":"0607.05047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085182$0B95B2E6-F228-4696-8D40-F25F8EEF723B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3b0daf85688f05cabffbe8eb8c089cc7ed0eede6","datavalue":{"value":"10.1016/0166-218X(86)90010-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085182$43A15C17-F6E6-475C-8BFD-75EA0382476F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2d176dcf8014bfec2c4899579ee7ce9e18294338","datavalue":{"value":{"entity-type":"item","numeric-id":166203,"id":"Q166203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1085182$46A3A364-0C6A-41B5-A09F-3AE0B1370B68","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":"Q1085182$20A61C7D-5B02-4A91-BF5E-42AE0A4E674B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1085182$3BAA310A-CA58-43E4-A55B-98E9E95613B2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bdbf3e3a59604760d419b8b8f368090448c1ee82","datavalue":{"value":"A graph G with vertex set \\(X=\\cup^{n}_{i=1}X_ i\\), for n given sets \\(X_ i\\), is called a feasible graph for \\((X_ 1,...,X_ n)\\) if, for each \\(X_ i\\), the subgraph \\(G_ i\\), with vertex set \\(X_ i\\), is connected. The authors consider the (NP-hard) problem of finding a minimum feasible graph. They give a sufficient condition, that can be checked in polynomial time, for a graph to be minimum. In addition, they show how every minimum feasible graph for \\((X_ 1,...,X_ n)\\) can be obtained from any such graph.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085182$86790B19-CC7D-44B2-9969-4137A5F0AC33","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085182$CD2F6E1B-C64C-4BF9-AB6E-62C6436855E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085182$3DDA4EE9-A098-46D9-996D-7E8A81E82D8A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1c2244e1684bbbf9921f0cce919d56b44e2370e4","datavalue":{"value":"3981214","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1085182$BD9E264A-A258-4A61-8616-71393EFAAD33","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085182$933236F2-8344-4D3C-9FD7-B4B00E39FAB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a1f8d541ada4dd96906cad1e2bf5e050022d93a","datavalue":{"value":"minimum feasible graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1085182$66DF3596-6F9E-499F-907E-3E59C38C066A","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":"Q1085182$CD636B0D-D87A-4EEE-A40B-8168C5E490E4","rank":"normal"}],"P223":[{"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":"Q1085182$109AE076-0C1A-4C82-AFF6-EDC6104AB5D5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83d2e6bc42e668be2d30db62fa082acbab18050e","datavalue":{"value":{"entity-type":"item","numeric-id":3470484,"id":"Q3470484"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82bef3b5cdc5807418811fc007c2af8fabf62495","datavalue":{"value":{"amount":"+0.8539572954177856","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":"Q1085182$E31222DC-4A6E-445C-AFE4-8E3884D05B2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1089420884e2fe22636e4ed2e31d93ed2590797","datavalue":{"value":{"entity-type":"item","numeric-id":1908609,"id":"Q1908609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90aa9be3c79aed23e9d4f223cc574198e2485ebf","datavalue":{"value":{"amount":"+0.8370387554168701","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":"Q1085182$00CA00EE-EB25-45EB-A514-C1BD188E193A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07e925e1a48515630bbaedab6a0551e464244cab","datavalue":{"value":{"entity-type":"item","numeric-id":4018996,"id":"Q4018996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4429728f8903413e7ff32839f06406774c31d14e","datavalue":{"value":{"amount":"+0.7773175239562988","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":"Q1085182$C5DED77C-F0FB-40C3-A7EC-63777B0A128B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c42bc1ce4e91bea186b19d630b29eeae0201762","datavalue":{"value":{"entity-type":"item","numeric-id":4035360,"id":"Q4035360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fe0ca6c2b591ebb6c8b016408ba6cdae99904b36","datavalue":{"value":{"amount":"+0.7735226154327393","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":"Q1085182$9D09F9EF-1322-4272-AAF3-84575D085A85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48176807f1d0eff0a1f59000f9c3d9fab77e6889","datavalue":{"value":{"entity-type":"item","numeric-id":1804586,"id":"Q1804586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91b98ea865eaa1710fdc6bcd1fa244fab8c49c69","datavalue":{"value":{"amount":"+0.7722833752632141","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":"Q1085182$BFBA1F3A-AB00-42F1-B519-AE229C30AFED","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An optimization problem on graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_optimization_problem_on_graphs"}}}}}