{"entities":{"Q686148":{"pageid":687997,"ns":120,"title":"Item:Q686148","lastrevid":63469410,"modified":"2026-04-11T13:22:46Z","type":"item","id":"Q686148","labels":{"en":{"language":"en","value":"Stable sets versus independent sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 427998"}},"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":"Q686148$3E1F1CD6-015D-43F6-A1E3-D574C1E5C79A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2a821057c263c43f4d5ac8154dd98aed0ea9b347","datavalue":{"value":{"text":"Stable sets versus independent sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q686148$821D8AD5-F0A3-4FA1-B564-31B4078F2E9E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fc65b1dd534ec49a6e305c2d7f397c213ae3d475","datavalue":{"value":"0783.05036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686148$6134FB1E-ADD5-46EC-AD1F-87F74973BBA7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bcaba3b67565fd5c1a352b6a58f94db1c6bf98d6","datavalue":{"value":"10.1016/0012-365X(93)90325-N","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686148$AA0FDE20-8E1A-401C-9FE8-99BBA77C13FE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"84b3ed84bea0d94201a16bb2ea3c8899c4642452","datavalue":{"value":{"entity-type":"item","numeric-id":281609,"id":"Q281609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686148$594A3EF9-BFDF-46A5-A474-2CE50178E97B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686148$C8B8C929-8854-4A00-920E-F01BD919E22E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"87ddefd6c83e22cbdb85f95663ace293dcff1d10","datavalue":{"value":{"time":"+1994-03-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q686148$358F15C7-C81F-4EC0-A126-6FB0851B2D21","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dd76926308631bc51b0f9d2764aaeb47e21d2998","datavalue":{"value":"The matroidal number \\(m(G)\\) of a graph \\(G\\) is defined as the smallest integer \\(m\\) so that the collection of the stable sets of \\(G\\) arises as \\(I_ 1\\cup I_ 2 \\cup \\cdots \\cup I_ m\\) where the \\(I_ i\\) are collections of independent sets of matroids on the vertex set of \\(G\\). Computing \\(m(G)\\) is shown to be NP-hard and various results on graphs of matroidal number at most \\(m\\) are given. Similar problems with ``intersection'' rather than ``union'' are also considered.","type":"string"},"datatype":"string"},"type":"statement","id":"Q686148$6C708BF1-BA72-4B59-8111-D4DCC5C7C57F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3a2423d4080d6028a3a8be7e0d0098fe6e3cd478","datavalue":{"value":{"entity-type":"item","numeric-id":226827,"id":"Q226827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686148$E2D947CD-AB81-46CC-A57F-58B54301FF2D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a06727f99c93aa58e84e3d476d4f6a1bed523458","datavalue":{"value":"05B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686148$CB7748DA-B0EA-4882-9145-141B88D9A91D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686148$1AD6A909-2B51-48CC-BF7B-324AEDB75CB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686148$42B17C2D-84A7-4E43-B3B4-C8B8EEFBCEFB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3845b0def1a37e8de59cbdfe4191acb08eda10f1","datavalue":{"value":"427998","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686148$60A35F27-823E-4F6B-9989-9E93F224DFA9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ff482bb55d7e7c9f8dd5c319cf5b16a9a217c1a","datavalue":{"value":"matroidal number","type":"string"},"datatype":"string"},"type":"statement","id":"Q686148$516FB0C0-7CAA-44E9-976B-E39FF97E49B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd271b779b62c7cd432d9f98fc97aaf6a61067e8","datavalue":{"value":"stable sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q686148$8139A3B3-D054-41FD-B747-0343F3390376","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9890d2d31de82fcf86b74b799289b36efeaabea2","datavalue":{"value":"independent sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q686148$7FF1C259-D0BF-403D-B2EE-679BC14CA942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a39ec4307b26d786312cb390856b9060d3bf22c8","datavalue":{"value":"matroids","type":"string"},"datatype":"string"},"type":"statement","id":"Q686148$7C9BE2F9-BB78-49B4-B949-108BCE9D62F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8f12ea105addea4e52f9511695748975bd61a49c","datavalue":{"value":"NP-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q686148$C26DDB33-DDDE-4A67-BAF9-673A4748C504","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":"Q686148$C6645080-A2D5-4CCA-B43E-5244F75EDE2C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f0d185962df00f58b50ee3eeb49a9796c86597b","datavalue":{"value":{"entity-type":"item","numeric-id":1063611,"id":"Q1063611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686148$8748996F-A611-450F-8E71-33572668679C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3a3980d0c975b0c936dae73c07de3e217dc8503","datavalue":{"value":{"entity-type":"item","numeric-id":3325492,"id":"Q3325492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686148$49EF09EA-0CDD-40FF-81DD-2029FF87284E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8e732ac24fced24328d5e2eb0ec178a3b48efbf","datavalue":{"value":{"entity-type":"item","numeric-id":4020706,"id":"Q4020706"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686148$6431A5A9-B52F-4DC0-BA71-C6B9E2B5003D","rank":"normal"},{"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":"Q686148$75B0F621-8A04-43BE-8B5C-2746EB2D01C6","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":"Q686148$E7E8C5C9-282B-496D-9E12-723F49784F19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58709679cfff7718457ae5dbfaa34a4e9b17219c","datavalue":{"value":{"entity-type":"item","numeric-id":5812263,"id":"Q5812263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686148$FF3EEE54-FDD0-4ACC-B3BE-98F20C568B92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686148$4387B9FE-7112-419D-BB32-C1F654E7CF99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"16ee6ba21410efd14ddd2a024a73c0ed4e5a2745","datavalue":{"value":{"entity-type":"item","numeric-id":4111952,"id":"Q4111952"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q686148$71CA2444-CB01-4DF6-8002-CBF9993218E3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f7519601e6dc908327535acff4f8d142cfbdbaf5","datavalue":{"value":"https://doi.org/10.1016/0012-365x(93)90325-n","type":"string"},"datatype":"url"},"type":"statement","id":"Q686148$25C1E4D9-CCBE-4F08-B50C-08CE2543EEDD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"bd4837ce99d4606463535b52fd7121ba389a3272","datavalue":{"value":"W2068255817","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q686148$938F56D3-A5E2-4607-A857-2A4AC683EC77","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa9163e24935b68a404840eb9bb4e40b3d235da2","datavalue":{"value":{"entity-type":"item","numeric-id":5752609,"id":"Q5752609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a908c4151258d94e0eb25ab0b7613cc068d27d66","datavalue":{"value":{"amount":"+0.8030492067337036","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":"Q686148$F9A83FD0-AC9A-4322-914C-AD1C296C9D68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"268c554213c400ef4d7cec81587857854a76712e","datavalue":{"value":{"entity-type":"item","numeric-id":4712205,"id":"Q4712205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea04dcc47d68de3fc39806acf8c11533414e4057","datavalue":{"value":{"amount":"+0.7893034815788269","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":"Q686148$D48E0A5F-9728-4858-AA94-75485BEC0640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e7ccab423933f0b45abe065436483ce71d259684","datavalue":{"value":{"entity-type":"item","numeric-id":4711754,"id":"Q4711754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a458c318a59c743695ec77161285a0f7c42b9b2","datavalue":{"value":{"amount":"+0.7829569578170776","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":"Q686148$9BC2FC62-322D-46AF-8352-0787623DBC73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c121e4cc181e1bde712cf3d4788872d870293c37","datavalue":{"value":{"entity-type":"item","numeric-id":3472146,"id":"Q3472146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cde58757bafb0526d3dd5473b7f58b6ae537f9c","datavalue":{"value":{"amount":"+0.781208872795105","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":"Q686148$1B1AA20C-996B-4E56-AE2D-D0039501EC7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd03623aac3092152bd3c56f183a561747e14add","datavalue":{"value":{"entity-type":"item","numeric-id":1850112,"id":"Q1850112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b36e8218a79126772b1e3c3370190eb994aa50f","datavalue":{"value":{"amount":"+0.7791050672531128","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":"Q686148$3B245AA8-9CBE-4684-89A0-E1258ADA2ADB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Stable sets versus independent sets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Stable_sets_versus_independent_sets"}}}}}