{"entities":{"Q1853148":{"pageid":1863890,"ns":120,"title":"Item:Q1853148","lastrevid":71501343,"modified":"2026-04-13T22:40:56Z","type":"item","id":"Q1853148","labels":{"en":{"language":"en","value":"Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1856484"}},"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":"Q1853148$D57751A7-9CC7-49FA-8227-2CFBAB6D8F55","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"282a34b644c92a45bb8b89e713394b6fab1f5841","datavalue":{"value":{"text":"Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1853148$44C32AD8-67E4-4E8D-8216-CD5E7EE6CE6E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"35f309483e7e7578a44e8255cdfdd4ccab7bb119","datavalue":{"value":"1042.68085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853148$8654546C-76F8-46BB-8BD7-140505646B4F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"873fe10d581be542051cecbcc2f4757a1ef20011","datavalue":{"value":"10.1016/S0020-0190(02)00291-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853148$BE339472-E4D5-4B41-859B-9C8FB0CB4F98","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbb68d9de22321af7fb543db220c0a16a741857c","datavalue":{"value":{"entity-type":"item","numeric-id":170457,"id":"Q170457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$F791DCC4-BEB3-4004-BBD6-A4359F4070AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1a48ab6bd1d2f76e62f44f1605c620679cbc8126","datavalue":{"value":{"entity-type":"item","numeric-id":868953,"id":"Q868953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$72043B17-5A47-4661-AEF7-F0A116D5B13B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$67143F3B-E66D-4C84-8A88-E72387EDCDC9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b5e42af6f5e314fbfeffbcec47ae99c9eed44fd","datavalue":{"value":{"time":"+2003-01-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1853148$6ACFE3C0-87AF-4C92-A76D-E4AC0F8BD889","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5646ee00fa6b181c7828f2366626fa4718c43b62","datavalue":{"value":"Minty has shown that the Maximum Weight Stable Set (MWS) Problem can be solved in polynomial time when restricted to claw-free graphs. We show that the structure of graphs being both claw-free and co-claw-free is very simple which implies bounded clique width for this graph class. It is known that for graph classes of bounded clique width (assuming that \\(k\\)-expressions can be determined in linear time), there are linear time algorithms for all problems expressible in Monadic Second Order Logic with quantification only over vertex sets. The problems MWS, Maximum Clique, Domination and Steiner Tree, for example, are expressible in this way. Moreover, we describe the structure of prime graphs being both \\(H\\)- and \\(\\overline H\\)-free for any four-vertex graph \\(H\\) and obtain bounded clique width for these graph classes except the \\(2K_{2}\\)- and \\(C_{4}\\)-free graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853148$C6AD6C2D-74B5-4B77-96D7-C332F00E0131","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853148$B1F79F72-9D41-4A79-9AB8-BEAE1C010B43","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"077018826645bc67d3a968e6dd43ba3965b1fa44","datavalue":{"value":"1856484","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853148$39B7A8EB-AEC3-4D4B-A41A-2A0FE6CC493F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c36be0e4965294df9d5c184769e1842e794d5d7","datavalue":{"value":"Modules in graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853148$EF7FE08E-C49E-452D-A736-C4AC00E99AD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"584c09af0dfa72320ab91cfef66b665de08fc276","datavalue":{"value":"Modular decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853148$225E16BE-8FC0-49E8-8255-BC831AEA9274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e51ed7fffd497e81c4385e1d78f55590b248c21","datavalue":{"value":"Prime graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853148$EBDF85E4-A626-4D34-8664-D4BCB5E7FCD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b263c0484c103f1a9d90abbbbe4653e49c9e4163","datavalue":{"value":"Clique width of graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853148$AC6B3BBA-4E42-44B2-9A73-5BA1D6D54166","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36c464b0825c34dd30e7c8f43c57da2250dc2185","datavalue":{"value":"Linear time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853148$6777CA30-1A22-493D-8503-7E20D10F241D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7af84995fb51d84a6b07ab24983d16c9003b35e8","datavalue":{"value":"Monadic Second Order Logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853148$FC8F9A2E-C1FD-4EAB-A511-7D76734FD5D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c98cbea13e6d3b3955e11ef96f0cfef8b30ebc28","datavalue":{"value":"Maximum Stable Set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853148$69E739F5-61F4-418B-A86C-906A8F5406C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8baf804bc4c1172cd32c9cc96b06a8c070f11c0c","datavalue":{"value":"Algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853148$658DCBCE-F9D8-4F00-8CE4-C67D6E22D7A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da67da54e89e7c80f20f3f95c3ceec18bb927753","datavalue":{"value":"Computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1853148$982CCA18-5680-4550-AAA4-450DE58D8231","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":"Q1853148$0A513E85-FFBF-4A39-9912-73183AD20214","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"282d88b529308441c287f6c692de7afeae122bdc","datavalue":{"value":{"entity-type":"item","numeric-id":4243764,"id":"Q4243764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$7091D7C1-D0C5-4375-9C54-46ADAAEBE14F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$019B07AB-0BA7-4FA2-BEA3-91F1E18B4A80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01daeab766d175bddc9f50c88df891bc3bb25b36","datavalue":{"value":{"entity-type":"item","numeric-id":3676177,"id":"Q3676177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$779CB339-D13A-48C9-8064-ED1806DC3752","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3edc2fe01664e7ae5dbedc60a81011b311142a1b","datavalue":{"value":{"entity-type":"item","numeric-id":3694709,"id":"Q3694709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$69443397-730F-4655-9588-757381705A24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7af2c5eca3bd22f8693a9ef2542f46a220d3edf1","datavalue":{"value":{"entity-type":"item","numeric-id":2366278,"id":"Q2366278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$F52084ED-36CC-4AF9-86DA-B9068FAAE349","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8fe56184955dbba620e4cb94dc309dfe37fcc19","datavalue":{"value":{"entity-type":"item","numeric-id":1974445,"id":"Q1974445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$62415EAF-C114-4079-B2FC-3DF31A2876A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"211530a7d66720062b60e82cf130f31beea4a662","datavalue":{"value":{"entity-type":"item","numeric-id":1975365,"id":"Q1975365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$9BC9694B-3CBF-4551-8299-8BAD73189D28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed91ed0176924a73cbecba9388f8a04535563e10","datavalue":{"value":{"entity-type":"item","numeric-id":4954442,"id":"Q4954442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$7B0EB830-9822-4992-BD52-793938233460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ecded16c6af01ba5305fc6d6c5c53e4149b079e","datavalue":{"value":{"entity-type":"item","numeric-id":5501779,"id":"Q5501779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$915E4E2D-CB1D-4DFF-BB1D-2354FC139021","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8add4627ebed45e331231c9fcb96d24b9b77ef2d","datavalue":{"value":{"entity-type":"item","numeric-id":4193514,"id":"Q4193514"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$0A927CEF-FC21-4053-93A2-F8FA5F04D385","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f8c15d74a0e0e55ad508fc6ba5d3dd313d05a1f","datavalue":{"value":{"entity-type":"item","numeric-id":5585189,"id":"Q5585189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$C36DD881-CCD6-4442-A478-C04987D4FF64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbe76e0762ef700f0ca9d7f733f0d5ad37484351","datavalue":{"value":{"entity-type":"item","numeric-id":3831058,"id":"Q3831058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$955F8688-B2A5-4AC7-A7E1-67F8C870E5CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8cfcd8d613906535ebdafef3a5dd83e49107cccf","datavalue":{"value":{"entity-type":"item","numeric-id":5249008,"id":"Q5249008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$E6883643-5E9F-4A94-A765-2B7A4E0BBEC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e405b7fbda3f49c85188dd1e8eaf0b9f0a8ade2b","datavalue":{"value":{"entity-type":"item","numeric-id":1301738,"id":"Q1301738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$AE10C66B-1E99-49CE-A1FE-FA656638A767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ada71f343b2168554ef3d8e68058bb18dbed1fd2","datavalue":{"value":{"entity-type":"item","numeric-id":1139605,"id":"Q1139605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$5FB322D6-F36E-4A61-9B6F-21E2CC3D0F79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93a0021bb8eb537cd0811e93c7490e7e9ba98e6d","datavalue":{"value":{"entity-type":"item","numeric-id":3683903,"id":"Q3683903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1853148$4D4A113F-94B1-4F4F-95A7-4765FF9CC26A","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":"Q1853148$0AF8741A-DA5F-4EE9-99B2-2F0EB7C7D7CD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"700ca405c5a9583325e73c32a034f539f7f22362","datavalue":{"value":"https://doi.org/10.1016/s0020-0190(02)00291-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1853148$A81DDE4C-D5E3-47C2-98AF-9AB945B825B0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b03424757e130f1f16e74d641002fcf4a748317f","datavalue":{"value":"W2082819223","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1853148$D5DB2BE5-6087-419D-8832-CE040776E878","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"089a461c2de39d7188968955b61a2730e324bc5f","datavalue":{"value":{"entity-type":"item","numeric-id":2227542,"id":"Q2227542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9671a8076badee0f0ba2a7015c3b107a9e9581b3","datavalue":{"value":{"amount":"+0.8671709299087524","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":"Q1853148$FFAD93DA-97F8-4917-B51C-FCCC0CB837C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d74325263dca13d14ae6cb046e3fb12cdf4abc7","datavalue":{"value":{"entity-type":"item","numeric-id":1751148,"id":"Q1751148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac16fe6f6a98239a21038e794bbc78bc4c9871ce","datavalue":{"value":{"amount":"+0.8576788902282715","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":"Q1853148$83D746A3-7D07-4DE6-A1A0-8CB6A06FBC3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7aa85842712d3f211625897f38459f1814fff1b9","datavalue":{"value":{"entity-type":"item","numeric-id":3503841,"id":"Q3503841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"720747ede84ba2970696ae483b80fb6ff9c7751b","datavalue":{"value":{"amount":"+0.8567851781845093","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":"Q1853148$441F8A76-14C0-4AD7-A61B-2953338FD06A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f91da83ca3c470c87051579d73c73fc3a437d00","datavalue":{"value":{"entity-type":"item","numeric-id":4782740,"id":"Q4782740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2f4b3539d1c1aec119db037696ef5aa35ca171c","datavalue":{"value":{"amount":"+0.8483014106750488","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":"Q1853148$DFDA62E1-E7E2-47DF-BBF3-D35214904457","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fd5116382aac1056bccab96b60e769b379568628","datavalue":{"value":{"entity-type":"item","numeric-id":1414581,"id":"Q1414581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2f4b3539d1c1aec119db037696ef5aa35ca171c","datavalue":{"value":{"amount":"+0.8483014106750488","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":"Q1853148$AE39A336-BE77-49A4-AE78-F1DAC359E3AA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximum_Weight_Stable_Set_on_graphs_without_claw_and_co-claw_(and_similar_graph_classes)_can_be_solved_in_linear_time."}}}}}