{"entities":{"Q1183338":{"pageid":1194087,"ns":120,"title":"Item:Q1183338","lastrevid":42307960,"modified":"2025-06-05T10:09:19Z","type":"item","id":"Q1183338","labels":{"en":{"language":"en","value":"Computing independent sets in graphs with large girth"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33083"}},"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":"Q1183338$D4E1F5CA-3ACB-42D9-838F-DBA5E5142F91","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9fff79dfe98248db095d5f0c4b4b8c13f456475c","datavalue":{"value":{"text":"Computing independent sets in graphs with large girth","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183338$108007E9-570B-45B7-8E01-85BD983C0898","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c98831da4bdb01db49b18afca3510c251312259e","datavalue":{"value":"0769.05053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183338$515562C2-F56E-4908-91C2-5F7B891542CA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e587f478522cefa2aa64186f25c7d28625b87c8b","datavalue":{"value":"10.1016/0166-218X(92)90041-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183338$423CBEDD-AA94-4396-A286-A404E36315F2","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":"Q1183338$B4DF6FEE-CF88-462B-8A0D-DAC477DD7310","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1183338$F6D46D6A-C52A-4FDF-AC29-467726FCF8F2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183338$BCDE4AA0-8EE4-4A70-BE7F-6A39AEF2286A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183338$ACE39304-F4C7-45E2-AD79-7732CE1D3AEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183338$0F8D2C5B-F59A-4E25-B322-CBC5C41D6262","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"31de9eaf2bfc621b6ae8cc9c9322e31d2baf8e2c","datavalue":{"value":"33083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183338$F26DDD36-065E-4735-8852-CAFACD4D151A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a1a173748f93e4f70aa784451677e2ec88ea88e5","datavalue":{"value":"girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183338$FD718514-6801-4457-8139-01103775B712","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a36f1f661169e98576879579295ecf0220457b9c","datavalue":{"value":"independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183338$CE612684-0FA6-46E3-BB5C-0BE5A2BDB272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183338$7C1C84D1-4A70-4C11-B843-7286F740FD5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f96c2fef07b016bb85f647d04605650c315e0f89","datavalue":{"value":"polynomial time approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183338$54BDA4AB-D802-4494-AD97-A5EBE7D5612A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"525614847f28c0ceee658bdd3b4593b887ae3ece","datavalue":{"value":{"entity-type":"item","numeric-id":910224,"id":"Q910224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183338$A94B577F-65E1-4D76-A253-DB7282DA6FAD","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":"Q1183338$1B1A4C19-0132-4FEC-A5E4-9EF598ACFC16","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b0ec9a9850e3c936b0e390e064fb78664790862","datavalue":{"value":{"entity-type":"item","numeric-id":4165387,"id":"Q4165387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183338$D67F89A5-58AD-4F59-9CD1-9759AC46B5C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27b91fb34b309a1448e42736f924e3a5012ab649","datavalue":{"value":{"entity-type":"item","numeric-id":3253064,"id":"Q3253064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183338$9585A003-702F-4EE3-9D58-BA73F2293527","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67085864f6a7b39588c06ae975acc511fd0f7ad6","datavalue":{"value":{"entity-type":"item","numeric-id":3872499,"id":"Q3872499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183338$F1C4ECD6-E460-438F-A66A-71E3FCEA8134","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e7d3dffde4b639a5080d558096cb7a34be71d72","datavalue":{"value":{"entity-type":"item","numeric-id":4146529,"id":"Q4146529"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183338$E6547BEA-CB18-4E4B-887B-C22EF4747049","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183338$D7C45E9D-D82B-4BCC-9393-DDF0047B20CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf6dd27ad1e0108f4014296aa58a9a489aabf84c","datavalue":{"value":{"entity-type":"item","numeric-id":1835927,"id":"Q1835927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183338$A89169CB-0E3F-4510-A1EE-5E6886D05582","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d94ec03eaf3d4dba495429ce59941b9503f807d","datavalue":{"value":{"entity-type":"item","numeric-id":3875951,"id":"Q3875951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183338$7E3F3E59-6A79-451B-BBF0-AEBA64C803EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"feab76b428109e405813ad604dda5709c195a1b3","datavalue":{"value":{"entity-type":"item","numeric-id":762496,"id":"Q762496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183338$D1E5DFEB-78A3-410B-9030-76EF10BF7D64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e81d90827a0aec8468b8c5d962de74cf4ef0e19","datavalue":{"value":{"entity-type":"item","numeric-id":1175993,"id":"Q1175993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183338$36978091-F6E9-4D12-8CDE-229C8F5D3067","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2a0983ce7a664c54ed4274f83ecbe33679a4f0","datavalue":{"value":{"entity-type":"item","numeric-id":4074668,"id":"Q4074668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183338$07F54E86-A61D-4458-88A5-73D095FF7894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ccf2ce6ffe932287a3e8f6d3b281b44fd4ad0eb","datavalue":{"value":{"entity-type":"item","numeric-id":4770411,"id":"Q4770411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183338$4B958CE5-73B5-443F-A7BC-6B59C4FE734F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa0e14bfd589a9ae5b8bb6ac61a529ec2f667fcb","datavalue":{"value":{"entity-type":"item","numeric-id":3864546,"id":"Q3864546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183338$7BE21DBA-24B8-4B84-BE6F-0F0DDBD9C8D9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68feda83064b9235d6297e7b7584b44ca3aa431e","datavalue":{"value":{"entity-type":"item","numeric-id":5317564,"id":"Q5317564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bee60f6f750d2cb3c0cb3f1bb702da2b7f296a2f","datavalue":{"value":{"amount":"+0.9424069","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183338$BA68D43D-5BF0-4F51-A6D8-22CC1995B503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8eb7d73a326967f810ad050468c2983df8629207","datavalue":{"value":{"entity-type":"item","numeric-id":2384807,"id":"Q2384807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"92f8ca33721184048d2b0a06378f96127cb4b74c","datavalue":{"value":{"amount":"+0.92784286","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183338$30F1303B-7C03-4EB2-9332-803BC5C83D07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"860d9b8e08c7baec367c7f54b1b8b263696e7c53","datavalue":{"value":{"entity-type":"item","numeric-id":2717906,"id":"Q2717906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"562bb6b0da4cc975e0f722adcb675742ba9924b7","datavalue":{"value":{"amount":"+0.91764665","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183338$BA2608F2-BFE4-42BD-9E6F-0B70271ABDF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24ef7d1331fb269897a84bf341a879b4aad9a6e6","datavalue":{"value":{"entity-type":"item","numeric-id":5363078,"id":"Q5363078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00309f88def6051194ad2f04ec413eae4e7f046a","datavalue":{"value":{"amount":"+0.9159967","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183338$3114602A-FE40-4C3D-9AC9-04D3D7D0A0C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee473969cbc688b90d4c9788e9224949e58d203b","datavalue":{"value":{"entity-type":"item","numeric-id":4400840,"id":"Q4400840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60ce2f282270c878b5546aabb1efb8f619b6f9ce","datavalue":{"value":{"amount":"+0.9148293","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183338$3B2E4FDC-F911-4008-9541-67F72BC365A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ecb1d8af9c9c2ec119d8ba39f1195a3d11ad3f1","datavalue":{"value":{"entity-type":"item","numeric-id":2333222,"id":"Q2333222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3ef6dfa02d16d7ab0325d79639f2a3d4b2cca47","datavalue":{"value":{"amount":"+0.9128735","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183338$CA089F59-CB0F-4874-BC7A-0ACE8FEA582A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"346b349e1f65391eaf0e57de4d1337958ce1f458","datavalue":{"value":{"entity-type":"item","numeric-id":1100485,"id":"Q1100485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4425916c6923b1a248f3a9bc840a7b1c706481a","datavalue":{"value":{"amount":"+0.9112623","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183338$F0369CD1-0E57-49DC-9230-A5FC2A3AD99A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ded8e615227f8b58882fad50178a6e63ab8a5d7","datavalue":{"value":{"entity-type":"item","numeric-id":3786498,"id":"Q3786498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9e6ec1c0a5e5e7ad8f950b7deae426a8405883d2","datavalue":{"value":{"amount":"+0.90937114","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183338$34911775-BBDD-4527-ADF8-42C47BA02AA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b4fe9f27c219d7906f838f9121d27a7634cb62e","datavalue":{"value":{"entity-type":"item","numeric-id":4252376,"id":"Q4252376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7f4a7115d5b02e732db548ee448a71ba8fa4be4a","datavalue":{"value":{"amount":"+0.9086758","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183338$6674F5CB-7CA5-4431-AA67-80C541F06B9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72da2dc0840ad6c3804fcc3b587bcc0555517ade","datavalue":{"value":{"entity-type":"item","numeric-id":5918655,"id":"Q5918655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e136a03b9e0fca4a464e2f00bc83c1317c33d0af","datavalue":{"value":{"amount":"+0.90836966","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1183338$E53144D7-BF5D-4C36-A1A5-F6572D7F4126","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1183338","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1183338"}}}}}