{"entities":{"Q488393":{"pageid":490160,"ns":120,"title":"Item:Q488393","lastrevid":52180499,"modified":"2026-01-21T02:46:20Z","type":"item","id":"Q488393","labels":{"en":{"language":"en","value":"Finding large \\(k\\)-clubs in undirected graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6390432"}},"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":"Q488393$2FB76A4D-F1F4-4D3C-A078-A62DAAE0500C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"25310023da9bc256a64a497d0f99ea733819524f","datavalue":{"value":{"text":"Finding large \\(k\\)-clubs in undirected graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q488393$48A5FE4F-0EA9-4C69-9551-B3D214863228","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"02834dcd805904fe005f2c213b3b637e528bffec","datavalue":{"value":"1310.05195","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q488393$BED78B6C-89AA-4E96-8C46-2C6895B888FF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5c35f5d32066d6b95640cdff3f46c055355e3670","datavalue":{"value":{"entity-type":"item","numeric-id":233432,"id":"Q233432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$77FBFEEC-1340-449E-8EC6-D8FBA6953B88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f26cba809dfdf4e3f5b8ad5bc273ca75d2891bd4","datavalue":{"value":{"entity-type":"item","numeric-id":306105,"id":"Q306105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$268D1808-E3C6-440A-BAB7-B0C542639280","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"67275743473f10103b3ca8cc327acbbf79695809","datavalue":{"value":{"entity-type":"item","numeric-id":488391,"id":"Q488391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$3F99372F-7162-46E7-8B13-856C73D7A073","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f3b3308675a0401f17b97880e9fceb8892130038","datavalue":{"value":{"entity-type":"item","numeric-id":488392,"id":"Q488392"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$3920D42A-ECC3-4B58-A534-7EC4B292657B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b79ece58f33b59758a066cb6b9ee149bab3a2c9a","datavalue":{"value":{"entity-type":"item","numeric-id":167642,"id":"Q167642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$08801C4C-D187-4A88-9546-9E7C94CB8DCB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e2211b1c56e0df95e4176061da2a32e641c42598","datavalue":{"value":{"time":"+2015-01-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q488393$64B064B7-F8A4-4DB1-B0AE-C93C1143ED2A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3f9250b0e8653ee21d69698dbc06c7a531e6e7b7","datavalue":{"value":"A \\(k\\)-club is a maximal set of vertices of a graph that induces a subgraph of diameter \\(k\\). Related concepts are \\(k\\)-clique and \\(k\\)-clan, see \\textit{J.-M. Bourjolly} et al. [Comput. Oper. Res. 27, No. 6, 559--569 (2000; Zbl 0955.91051); Eur. J. Oper. Res. 138, No. 1, 21--28 (2002; Zbl 1008.90048)]. This paper presents a branch-and-bound algorithm computing a maximum \\(k\\)-club in time \\(O^\\ast(1.62^n)\\), and a heuristic for the same problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q488393$1D322220-28B3-4BF7-AB7D-A6AB3FF36F30","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q488393$CCAFFE58-09DC-45D0-A88C-806D4E42F101","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q488393$9CC88C23-E581-4B5A-8C6E-7D7991A9F370","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9cf44d503e7d4771a74e60c8b165d38259abcf57","datavalue":{"value":"90B10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q488393$F9EE1DCE-2916-481F-97E1-B90C42348B98","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"af80ccb5a92b5c1a3aa2f2ab7f2427124ce41dc2","datavalue":{"value":"6390432","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q488393$13EFCAE0-42DE-4523-8573-F7AA09F86D66","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cdc6164cf25ab131dbb818bbd16bab28b6f9d095","datavalue":{"value":"branch and bound","type":"string"},"datatype":"string"},"type":"statement","id":"Q488393$86B7FB05-CFF8-4B33-8E0D-B65ECC2E9C99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5254fbc7af723cadda5d0002e4e5b9f94bff61d2","datavalue":{"value":"\\(k\\)-club","type":"string"},"datatype":"string"},"type":"statement","id":"Q488393$EBE11459-F155-45F3-87C6-804BE8378FE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"329bec8fe3dedcaecc68cd54d00b4ff442749a08","datavalue":{"value":"\\(k\\)-neighbourhood","type":"string"},"datatype":"string"},"type":"statement","id":"Q488393$2A1EC3AA-E41E-46A2-AD68-8C0D0CCA491C","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"2a216d6c09dac0df49b00b19ed2bb5c4336ef7f4","datavalue":{"value":{"entity-type":"item","numeric-id":20231,"id":"Q20231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$A3437BD3-D73A-498A-ACF9-602452EB016F","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":"Q488393$1C31612E-B16F-491D-95F3-20C87D247FCB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2d4072882debc7faa682b2dd16ee16ea3a8a4a21","datavalue":{"value":"https://doi.org/10.1007/s00607-012-0263-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q488393$4C1CF26B-61A5-47D0-BE98-770BEA37A201","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3f45df90eb5cf260ea2620e41df14cc8de258fb2","datavalue":{"value":"W1988659376","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q488393$B5EB9DED-DE30-4EE0-8AD1-1ADC9C17F305","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"133387f50eb5e74cb8219001369a71e98e61afce","datavalue":{"value":{"entity-type":"item","numeric-id":4051973,"id":"Q4051973"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$9C88FB19-ADEF-4686-831F-F5D4318ADC89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b4443b4e87afd9806709aa9144180d8f65c52644","datavalue":{"value":{"entity-type":"item","numeric-id":5326766,"id":"Q5326766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$AB0A8DB1-76B8-4B63-BE80-F71B999DD769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de16d53d376532f5c16a6176cd23236bf32145e8","datavalue":{"value":{"entity-type":"item","numeric-id":3557054,"id":"Q3557054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$6E66C3B2-21E8-4757-B762-80EFE088B382","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e68936b098b1555ac5e6d04b6a0a9c99c0e119e","datavalue":{"value":{"entity-type":"item","numeric-id":2576439,"id":"Q2576439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$EFFCDE2A-D61F-482B-842A-C6553BD4396F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b84b02ffb64989170f9119fa93d20c33798bd91","datavalue":{"value":{"entity-type":"item","numeric-id":1977620,"id":"Q1977620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$B6FFD475-6F9B-4202-82BF-529F6CCDECDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e13537ff691483a912f6d6ff92f69525754af446","datavalue":{"value":{"entity-type":"item","numeric-id":1600883,"id":"Q1600883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$67AF1E19-58BF-46C9-9DEE-A7C0195A1A9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1906bf3f2982dc71308ad6b749b526435dc3aa7c","datavalue":{"value":{"entity-type":"item","numeric-id":541693,"id":"Q541693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$DF0C9D62-CD7F-48F1-B29A-FF3D288B98F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbba1e94dac698478d700605005f4f3274714185","datavalue":{"value":{"entity-type":"item","numeric-id":5435671,"id":"Q5435671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$1A746EE3-3F1A-4910-859B-D0024E067525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"495a4cd5dcd3da63be973fad09e65764e4c24555","datavalue":{"value":{"entity-type":"item","numeric-id":4745163,"id":"Q4745163"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$F5033884-87CB-4A2D-8256-88D1BB0EFFF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc59d04b19ac0708078e0712ef24d993e3b0ae24","datavalue":{"value":{"entity-type":"item","numeric-id":4672747,"id":"Q4672747"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$C165CA0A-FEA1-450D-BA06-235F5B7A932F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f77347970e953e82d8dddf1fddbdb2c14d24ef6","datavalue":{"value":{"entity-type":"item","numeric-id":3452221,"id":"Q3452221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$A8214DE1-7883-4AE6-93EA-6FACFE419D1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bc033f499e92c96f3713d150c527b2e5b2fe2c4","datavalue":{"value":{"entity-type":"item","numeric-id":5047157,"id":"Q5047157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$F402596A-41A7-4DB2-BDEF-0912AA617EA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49a8681080ea8a8f60d9f133b96a95aee557c3fe","datavalue":{"value":{"entity-type":"item","numeric-id":4943078,"id":"Q4943078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$C034DB52-C46A-4CCF-8C45-0316BEC1BF9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6b447bbdd5520932298eb6c9a8eb840587618b3d","datavalue":{"value":{"entity-type":"item","numeric-id":2367014,"id":"Q2367014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$CEA86F9F-B6A1-4A2D-BDE2-47FC405CD30F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab1bcf0c29c42fe0df1ce237e135d5117a496390","datavalue":{"value":{"entity-type":"item","numeric-id":4899256,"id":"Q4899256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$7788E3D9-6E18-49F3-B468-9E811C584853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e1c277393b9383fcd1dc49a7b9f8d3b839eb3381","datavalue":{"value":{"entity-type":"item","numeric-id":3994557,"id":"Q3994557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$16F941F6-BEC9-4EE5-8CAF-A67794087881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8802396d6d653062718814dd3b9ff34b6644ed58","datavalue":{"value":{"entity-type":"item","numeric-id":3583579,"id":"Q3583579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$024B67DA-EE2B-4C47-B989-B0610B3FA378","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fbf9354f51c8ed3dd31dbcd18baffdd5a4defce","datavalue":{"value":{"entity-type":"item","numeric-id":1758028,"id":"Q1758028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$693AAF51-B82B-40C2-91AC-6FC2991A0A42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c14526e27b8d38edb621e57a0d5aff31478fa6f5","datavalue":{"value":{"entity-type":"item","numeric-id":448967,"id":"Q448967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$60FA0F55-A1CD-4862-8174-611D2844BF57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e91e61b03e4a92a6a205a2b6f7313081eb7cb1e","datavalue":{"value":{"entity-type":"item","numeric-id":385488,"id":"Q385488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$435EE520-AAD5-4C63-82CE-F70A59B4F9F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5490d81fe753efa90dd4eebc3e5dd4ca9f51aad9","datavalue":{"value":{"entity-type":"item","numeric-id":439496,"id":"Q439496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$D455ED8A-7494-40F8-8659-2DDF66AD8CAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"003bc6c20bd1d8ced7d2a1dc42f1b9c84a55618d","datavalue":{"value":{"entity-type":"item","numeric-id":4397004,"id":"Q4397004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q488393$17B3662A-1D77-46DC-A6B0-55C3E2AFB188","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"89cd8ce6d50fa8a9a7c29d670ae9c073d11be97a","datavalue":{"value":"10.1007/S00607-012-0263-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q488393$E10EF7CC-D97E-4667-B241-6ABD55FD44B1","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6082946b50d4b61dca67020f2176dcdf11379382","datavalue":{"value":{"entity-type":"item","numeric-id":385488,"id":"Q385488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c059c87543bc78e63367870b38ed9a901163a21","datavalue":{"value":{"amount":"+0.8948171138763428","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":"Q488393$39A1D834-81AE-461A-9BA3-04E0554F8630","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60d94bad587af02a4437882be219228aedda6f07","datavalue":{"value":{"entity-type":"item","numeric-id":1977620,"id":"Q1977620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6aceac677a8c50a48d855be85e7e10c74cf34e9d","datavalue":{"value":{"amount":"+0.886422872543335","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":"Q488393$6BBFC85F-194F-40A3-931C-FF82D05954A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10b0e16c158e70ad4338dc492d5b0d3d06b69d3b","datavalue":{"value":{"entity-type":"item","numeric-id":448967,"id":"Q448967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"12f4578d4fcf5eebb703165d81925033a635d407","datavalue":{"value":{"amount":"+0.8568658828735352","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":"Q488393$721A7702-E86C-454C-B435-F50C7454D9B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8de1a3a76485d20d311fe577d8002aab78a2330e","datavalue":{"value":{"entity-type":"item","numeric-id":1634801,"id":"Q1634801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11d7cc7dfd254780e52eb03dabb10f751a9b8173","datavalue":{"value":{"amount":"+0.8091867566108704","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":"Q488393$1DC618B5-DF14-4CA7-BA82-F7F68F51D458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d619b1517495411088846171f85d946c1e651537","datavalue":{"value":{"entity-type":"item","numeric-id":1600883,"id":"Q1600883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63ad1e9750ec9ab60010cf6684b1fd210022f006","datavalue":{"value":{"amount":"+0.8040777444839478","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":"Q488393$12443D47-054D-4B1B-AAE4-01B3D7B28B37","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:488393","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:488393"}}}}}