{"entities":{"Q2392036":{"pageid":2402779,"ns":120,"title":"Item:Q2392036","lastrevid":51792152,"modified":"2026-01-20T01:44:43Z","type":"item","id":"Q2392036","labels":{"en":{"language":"en","value":"Finding minimum clique capacity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6195497"}},"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":"Q2392036$B6D3EA4A-4EA6-4E9A-A980-BABC16520391","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1a4dba2b3f36e01cd9f5d023e51394f41c97438d","datavalue":{"value":{"text":"Finding minimum clique capacity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2392036$FE63E599-9255-4005-9C25-4550059091A9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3158da351f205d2eade45ea1a0cfaa36e41ba030","datavalue":{"value":"1289.05371","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2392036$A4F6EB0D-25E4-4967-9B72-DDFFC405B6A5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"86791d2de8f741697c1a28c841b5e520b1ea6f17","datavalue":{"value":{"entity-type":"item","numeric-id":256974,"id":"Q256974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2392036$6B58D2CD-98F3-4C7E-89C5-8AAB1805ADC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6c9c8d991cb59f8bfb573d1c78b1770eda9953fc","datavalue":{"value":{"entity-type":"item","numeric-id":256976,"id":"Q256976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2392036$6133C17C-3239-4E66-8CEF-4691424601CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b7666b1aea36d852e5d73efdf8f9faa64e3f54f","datavalue":{"value":{"entity-type":"item","numeric-id":705887,"id":"Q705887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2392036$66EBDC23-BFAE-4D24-8C3F-3D83A3280F9B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2392036$522D9E6D-0079-4FED-87FE-FC19D079D1D7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1b9371a1396b5660d5734cb5e0075d011d357893","datavalue":{"value":{"time":"+2013-08-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":"Q2392036$737E464E-A74F-4C28-B158-1630E8D8BB83","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7713d092e38ad55904a29c02d1661481f9c9c62c","datavalue":{"value":"Let \\(C\\) be a clique of a graph \\(G\\). The capacity of \\(C\\) is defined to be \\((| V(G) \\setminus C| + | D|)/2\\), where \\(D\\) is the set of vertices in \\(V(G) \\setminus C\\) that have both a neighbor and a non-neighbor in \\(C\\). The main result of this paper states that there is an algorithm, with running time \\(O(n^{3.5})\\), which with input an \\(n\\)-vertex graph \\(G\\), finds a clique \\(C\\) in \\(G\\) with minimum capacity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2392036$852B4916-1D67-4C8B-B9B1-1A68ED134B77","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2392036$88BD7EAA-9AC3-4F88-8D70-23A1BC37E972","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2392036$D88B60C0-477E-4BBC-9A46-5432594D7B4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2392036$2BBD49F7-C99A-4FEE-964F-5ED3EDBD9B5B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"abbfe140b70b27b7b591dd345d079f707d3c56d6","datavalue":{"value":"6195497","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2392036$E384C878-2D77-416B-BCDC-00A98887EB64","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"17b956dbfb7a118eab36a9d84411389cc7585533","datavalue":{"value":"capacity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2392036$B5E32315-0A23-4BEA-93C5-762F289B24B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdefb28951ee63f397ce9368bae3e97a2589921e","datavalue":{"value":"Hadwiger's conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2392036$0BC774B9-983B-4902-ABEE-03B7D74D268B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"093ef3cbea03ec661dc66ae3009ad13581b7249b","datavalue":{"value":"packing","type":"string"},"datatype":"string"},"type":"statement","id":"Q2392036$B2F3ABB4-E770-4F63-A18B-27CEBA2A7F29","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":"Q2392036$483542C5-E68F-4B8B-8E71-487B21D9FF2B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9ad9eaeac271a26ab90f269df4d811bc7cde46b6","datavalue":{"value":"https://doi.org/10.1007/s00493-012-2891-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q2392036$BDDCCA60-2CFE-46CE-8ECB-C5B868D816FC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f1958d1ee4f7a3735bbc9cc15173cec7c3ef8e09","datavalue":{"value":"W2121150643","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2392036$74708A4C-84C8-4C5D-A66A-C901C7C93C03","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c74b8fdf1182b274bba211b9edb5894595d6a331","datavalue":{"value":{"entity-type":"item","numeric-id":2392035,"id":"Q2392035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2392036$ABFA24BD-D7AC-43AC-A45B-9EBA362BC971","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187e1fb158e6b4695b1eefc466a8e0535eaf95e7","datavalue":{"value":{"entity-type":"item","numeric-id":5682014,"id":"Q5682014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2392036$B64F7F01-A416-411D-B2B9-342902088EB2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8605206605346da0667e720bae2cd76a63bbf543","datavalue":{"value":"10.1007/S00493-012-2891-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2392036$4B948CDB-3970-4AE2-832E-B4CA3D40E154","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0905548df64f2015ae1331bf99918b68d8346d5a","datavalue":{"value":{"entity-type":"item","numeric-id":5925264,"id":"Q5925264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d695d2c64fc0b43ef6fe891032a73eeab03e543","datavalue":{"value":{"amount":"+0.7290244102478027","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":"Q2392036$04BEBE48-86BF-4944-A06C-004364917417","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d752ed8ddfe5ad3a3b8231f54e74eaea57f3afb","datavalue":{"value":{"entity-type":"item","numeric-id":2456374,"id":"Q2456374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bda8212f8c8a59baea69ca5d8fae75b19885fe6","datavalue":{"value":{"amount":"+0.7203851938247681","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":"Q2392036$C532F247-8360-4F24-82F4-7C35E6689257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15a9907d91c4bf631d8361d539eb3eb8407c58fa","datavalue":{"value":{"entity-type":"item","numeric-id":3499731,"id":"Q3499731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6b0223b202524eb3299c5310ede6234ae835eb6d","datavalue":{"value":{"amount":"+0.7191315293312073","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":"Q2392036$C0153C1F-BBDC-41E2-B679-147948A4FED0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b755c9960ba24d7b3799dd3c4f4f9aceadcb9d9d","datavalue":{"value":{"entity-type":"item","numeric-id":477680,"id":"Q477680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b553690a09b1c5eaac285902b695f84d42ad6fb4","datavalue":{"value":{"amount":"+0.7169507145881653","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":"Q2392036$47D39088-7734-4F9E-B9BA-24B5059DF081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a864b43cd7fa28ac73f3f3d4839a408998d87df","datavalue":{"value":{"entity-type":"item","numeric-id":483409,"id":"Q483409"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36953c4d830c6ef24e37af8616b552634a4c53d5","datavalue":{"value":{"amount":"+0.716718852519989","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":"Q2392036$001DBFE8-0BAE-4E6C-8362-ABDBAF4F2C16","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2392036","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2392036"}}}}}