{"entities":{"Q1894362":{"pageid":1905104,"ns":120,"title":"Item:Q1894362","lastrevid":69214038,"modified":"2026-04-13T05:31:34Z","type":"item","id":"Q1894362","labels":{"en":{"language":"en","value":"Polynomially solvable cases for the maximum stable set problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 777824"}},"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":"Q1894362$5141D8F4-170E-4B51-927B-505C019FBCE5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4209564ff62fdd0eb1cba648203160e98143ea5a","datavalue":{"value":{"text":"Polynomially solvable cases for the maximum stable set problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1894362$7DCFD67F-499E-478A-B2A8-8B7A007308AC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"34a0a1e92fc42ff01b3d5f9f69d784e01493492c","datavalue":{"value":"0830.68099","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894362$EC589FB4-B2CC-46AD-A9E0-A3AE04DE83F6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"af2c8f701257dc1c68a5df5be4b84139e0c061e3","datavalue":{"value":"10.1016/0166-218X(94)00051-E","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894362$EEA053F6-C80D-47BE-BDDC-6F068493EFEC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4249c9a7a0b14df0599e70315ca2a040457d857c","datavalue":{"value":{"entity-type":"item","numeric-id":260023,"id":"Q260023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894362$269DD7E0-9BC2-4B47-BE8C-E31A459EC7AF","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":"Q1894362$12C78FC0-8A8D-448B-836B-72E66B84C29D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c2e4d7b864b259e9d648a2b76b651e0f4df79666","datavalue":{"value":{"time":"+1995-09-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":"Q1894362$CB29E13A-5353-48CF-812E-AC25A914B34A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"318767cfbb358a5b978fa37a0ebb3d3c523ff2cc","datavalue":{"value":"A set \\(S\\) of vertices in a graph \\(G= (V, E)\\) is stable if no two vertices in \\(S\\) are linked by an edge. The size of a maximum stable set in \\(G\\) is denoted \\(\\alpha(G)\\) and is called the stability number of \\(G\\). The author describes two classes of graphs for which the stability number can be computed in polynomial time. For one class, an iterative procedure can be used. At each step, the iteration builds from a graph \\(G\\) a new graph \\(G'\\) which has fewer vertices and has the property that \\(\\alpha(G')= \\alpha(G)- 1\\). For the other class, the existence of a stable set of given size \\(k\\) can be determined in polynomial time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894362$AE8B1683-E4DE-4B08-BBED-61FD99D17774","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894362$3C9CE2F8-92AE-4F01-AEFE-841D05317124","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894362$E28E48B3-92DD-4F04-A839-310C8F37A969","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894362$A8AF93B7-CB8A-4138-8F87-3DA1CAA2A11E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894362$962E3C2D-8B25-4835-805D-2D6207D2C327","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8d53edeacdd221254dc360c3d0dded658565e712","datavalue":{"value":"777824","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894362$FC409ACF-4F00-4A27-B567-1E18D7B951ED","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894362$77D5C705-3496-45AF-BD38-ABA9ED938588","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6dd0d7043066fc18c97c64cc2373bc266c0fadc1","datavalue":{"value":"stable set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894362$0CD45026-AA31-4435-8FAD-08A396D4EE81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87e0e2197df31604dd9f16334c9c805616d74d2d","datavalue":{"value":"stability number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894362$A8F8D258-3FA5-450B-B423-40A137240D89","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":"Q1894362$869A181C-0587-42C6-B848-9BD92892CF77","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f091a2487faa4320a607c7fc5ddd1d40ffc78957","datavalue":{"value":{"entity-type":"item","numeric-id":5615282,"id":"Q5615282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894362$AE953115-2EFE-4F0F-A94D-DAD046E0E8A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c9357d9f02862d3ff5a0fd97f68d2dc687dbfa6","datavalue":{"value":{"entity-type":"item","numeric-id":1208469,"id":"Q1208469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894362$959EA621-6CDD-432B-BCBE-058E5E8873BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be9a4b27634123dce7235d0ac0c37ee1217fc4f7","datavalue":{"value":{"entity-type":"item","numeric-id":3682509,"id":"Q3682509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894362$0EA4BD24-FBB2-4464-8C93-88070C737EBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65d469922887779d18bbf3fd4f31925af73b9db9","datavalue":{"value":{"entity-type":"item","numeric-id":1262136,"id":"Q1262136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894362$37DC76C2-9CB9-483E-BCB6-76EEBED51318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e65d73ae8ce50631a13a2e25599a048bc2eda73","datavalue":{"value":{"entity-type":"item","numeric-id":4158479,"id":"Q4158479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894362$E1DD60B0-9D26-4308-9629-02665238A67E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"372062ab71daaf29e9e9d082cc69fa4e57387087","datavalue":{"value":{"entity-type":"item","numeric-id":4018159,"id":"Q4018159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894362$B92BB50E-F156-49AA-8D65-DE8FE9104DC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70932f1cf740819121b6dff2db80775f668b9c68","datavalue":{"value":{"entity-type":"item","numeric-id":3216686,"id":"Q3216686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894362$E7E39AD3-5EB6-46FE-B5AF-1B0A27E0AEB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1520658579983937d57617c380bbcd46c2e4d2b","datavalue":{"value":{"entity-type":"item","numeric-id":762505,"id":"Q762505"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894362$73B88C42-0495-4DA7-A753-850060FDE89D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"974ebda8b7969127d2e6a9dc9704cb8e040cc76f","datavalue":{"value":{"entity-type":"item","numeric-id":1068855,"id":"Q1068855"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894362$DC8D1AB4-02C0-466A-A95E-83AF5FBB0AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ebfa07ef1e4191dcc1393d91efc1348dc0066d8f","datavalue":{"value":{"entity-type":"item","numeric-id":4693344,"id":"Q4693344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894362$88A9D974-18B0-4890-AAA7-A971F176C401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4c570bda964b76e5755c02e78b4470318c201fd","datavalue":{"value":{"entity-type":"item","numeric-id":1080863,"id":"Q1080863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894362$12E280A1-8CFC-4CF0-B5B4-94874104C130","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894362$2F6D61CB-08B5-446F-82C7-34910CB5D4F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f98527e95e30b0522da5b0d1ff72ede7cfbae1f8","datavalue":{"value":{"entity-type":"item","numeric-id":1144589,"id":"Q1144589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894362$6DC7F327-45D8-47DF-90F2-2BAB5177E069","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c4c0d5324bcc72ab97df3dacb6136d4acc23ee4","datavalue":{"value":{"entity-type":"item","numeric-id":1313833,"id":"Q1313833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98beb756397b1a4d33b1e262df71cc97629a1e57","datavalue":{"value":{"amount":"+0.8396793603897095","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":"Q1894362$EC694917-A688-4690-A511-62CE313C98B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab1769551eb1194bc658c736115ef24e3ff4005c","datavalue":{"value":{"entity-type":"item","numeric-id":4693344,"id":"Q4693344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dcae70db9b58f32ec0953061fd4bdaa11787b38","datavalue":{"value":{"amount":"+0.8376700282096863","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":"Q1894362$C4D69B2F-CF7D-4363-985B-62AB2BABFB67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36e7bf766a944e36152c00bfe256db25f520bd93","datavalue":{"value":{"entity-type":"item","numeric-id":1411110,"id":"Q1411110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f6d0fbf5a6cfcce611744f6e8131fca05500b79","datavalue":{"value":{"amount":"+0.8077437877655029","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":"Q1894362$655FB143-9260-4AEF-B3FA-020CBAFD549D","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":"ff60cde50b2d70e9edfab32e4efc48cb96859332","datavalue":{"value":{"amount":"+0.8075757026672363","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":"Q1894362$C3182EBB-AC30-41FD-9F4E-F990F0D5AC9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b79910975ae6b757427852d35905b62edc84739","datavalue":{"value":{"entity-type":"item","numeric-id":4780523,"id":"Q4780523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"76c00d43c5d73011d48723a2272a918beaf0046f","datavalue":{"value":{"amount":"+0.807564377784729","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":"Q1894362$99A9B6CF-982A-4EE7-A833-0986E11739C4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polynomially solvable cases for the maximum stable set problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Polynomially_solvable_cases_for_the_maximum_stable_set_problem"}}}}}