{"entities":{"Q2633284":{"pageid":2644027,"ns":120,"title":"Item:Q2633284","lastrevid":56824122,"modified":"2026-03-23T17:08:56Z","type":"item","id":"Q2633284","labels":{"en":{"language":"en","value":"On finding and enumerating maximal and maximum \\( k\\)-partite cliques in \\( k\\)-partite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7052222"}},"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":"Q2633284$2351A408-FBCE-4D8D-9437-3DF2B7069075","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"999a01dac611eab5457542f21d7b17afdb7d89c6","datavalue":{"value":{"text":"On finding and enumerating maximal and maximum \\( k\\)-partite cliques in \\( k\\)-partite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2633284$FBEEC106-58F2-4EDD-A43A-1011E5ED20C7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1b9a66c7263c36d21e2d5c32d837f947f711e1ea","datavalue":{"value":"1461.05220","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633284$2C50363A-3FE0-43C1-98F5-E51E95DC1050","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$47CC5A65-5876-4D04-BB32-EFC3A7EC6069","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$B67C18C9-067C-450A-A69B-56D96881A02A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8721ec9cf8de43034be561afa7e535bafe3c2e57","datavalue":{"value":{"time":"+2019-05-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2633284$39C46F37-E0C9-4079-B284-8AB7B6538012","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3c2242ead1efb39d090218b8655120064b878e62","datavalue":{"value":"Summary: Let \\( k\\) denote an integer greater than 2, let \\( G\\) denote a \\( k\\)-partite graph, and let \\( S\\) denote the set of all maximal \\( k\\)-partite cliques in \\( G\\). Several open questions concerning the computation of \\( S\\) are resolved. A straightforward and highly-scalable modification to the classic recursive backtracking approach of \\textit{C. Bron} and \\textit{J. Kerbosch} [Commun. ACM 16, 575--577 (1973; Zbl 0261.68018)] is first described and shown to run in \\( O(3^{n^/3})\\) time. A series of novel graph constructions is then used to prove that this bound is best possible in the sense that it matches an asymptotically tight upper limit on \\( |S|\\). The task of identifying a vertex-maximum element of \\( S\\) is also considered and, in contrast with the \\( k=2\\) case, shown to be NP-hard for every \\( k\\geq 3\\). A special class of \\( k\\)-partite graphs that arises in the context of functional genomics and other problem domains is studied as well and shown to be more readily solvable via a polynomial-time transformation to bipartite graphs. Applications, limitations, potentials for faster methods, heuristic approaches, and alternate formulations are also addressed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633284$83C63C82-0BAF-4142-9FF1-27C855B88CDC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633284$CCF3B284-A468-44A8-9E0D-A887B139E48B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633284$05A9F4CA-6DCF-4ED0-A692-2F2DEB61C091","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a12c61a6060093b035501a70bf88ca1d3e49803b","datavalue":{"value":"7052222","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633284$BDF892F4-2B46-4542-BC9F-2D9E6F87D4E1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3b495ba8c3c3bf5babb1d3213a6c0bf58078e5","datavalue":{"value":"graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633284$4BEBCD4C-78FF-4858-AB81-DC126CFF5297","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"584b864cea23f60ab2b00e479e2b0588f3493156","datavalue":{"value":"multipartite graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633284$5985A40F-781A-4045-A209-02B990F3ED32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f115a81543b37fe4640b1c297f0c9115ab3eeff5","datavalue":{"value":"maximal cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633284$A66C5CF5-9670-491C-A5B3-A1571BB4135E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a5affd82c191ca90d8a0be3acf9ed7c3dcc7233","datavalue":{"value":"dense subgraph enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q2633284$59E40F6E-675D-4E7C-9017-25DF096067B0","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"0bd02c26dee295e17fa1661a740b0e3277993f7d","datavalue":{"value":{"entity-type":"item","numeric-id":37543,"id":"Q37543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$D6B1F6C3-F176-42C1-9367-E9F761F438CB","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":"Q2633284$CF97A94A-1AB9-4038-9B3B-B743ED405A35","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"39bffc41e4f2ae1f257d84144a637d7c5f84d92c","datavalue":{"value":"https://doi.org/10.3390/a12010023","type":"string"},"datatype":"url"},"type":"statement","id":"Q2633284$79FE300A-1464-4450-99D4-7F04E3A5C9B2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e799c5b4ba011254d0da05f71359044c9b23284b","datavalue":{"value":"W2910185186","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633284$0DD25E67-9397-4C37-8A41-54BE10610CA9","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"ce78e8d93043f57cfc41b350e91d0ec080c91d46","datavalue":{"value":"Q92859027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633284$C7A88E5E-4DEC-4CF0-8C4F-7F8FF417DBCB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9db781ea163ae4f052d27a9093ccceac873e393c","datavalue":{"value":{"entity-type":"item","numeric-id":5955469,"id":"Q5955469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$F22D777E-02BB-48B4-B0D9-00C8CC506C2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92901e7307c615f66cdb25e8a294766737214a08","datavalue":{"value":{"entity-type":"item","numeric-id":2632355,"id":"Q2632355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$3F860F59-CCD7-4819-AFB0-239D3DEA19BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2767b58e368a93ef7a71bdedf7477c53d8db33ba","datavalue":{"value":{"entity-type":"item","numeric-id":4870046,"id":"Q4870046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$78277381-C795-414F-B2EE-C76BC8FB8BE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"501aefe4754342fb8d5444baacca037714207964","datavalue":{"value":{"entity-type":"item","numeric-id":4999425,"id":"Q4999425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$3FC75B3A-221B-40E9-8E88-305025D56C33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"078e0a5ec559210a14a4145be98e18a1a255f6b1","datavalue":{"value":{"entity-type":"item","numeric-id":5677064,"id":"Q5677064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$17C5DA1F-9414-4FBF-B7F3-57B45A9BAEB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3edb87e1b6352d7220cf8e3669d6c8551a9b12f","datavalue":{"value":{"entity-type":"item","numeric-id":860810,"id":"Q860810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$00458764-F53A-4072-809A-507FA9E8928A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df13cdd536d50039c70eeb4edb322a622623b0d4","datavalue":{"value":{"entity-type":"item","numeric-id":5266538,"id":"Q5266538"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$BC3CB6AC-3C6D-437D-8B17-B8749B9CD4C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23e24af53c970fb4aa7bd4b9590d9f76e4a7a60b","datavalue":{"value":{"entity-type":"item","numeric-id":360493,"id":"Q360493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$B266C8F6-0267-44B7-AE02-274BF52D9EB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a700db12d35919903ce0c2784e58dbd1487eec1","datavalue":{"value":{"entity-type":"item","numeric-id":5315378,"id":"Q5315378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$38290C72-2011-4F4C-B47F-81914C381D22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65c334f24f0ea0f5930a0f10f3816e5cbac17eea","datavalue":{"value":{"entity-type":"item","numeric-id":5920767,"id":"Q5920767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$ED73A7D7-C8C5-454B-BC04-DC9D0E7606DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efffaa25c80a8df95a6644b30927a447291f5378","datavalue":{"value":{"entity-type":"item","numeric-id":2428684,"id":"Q2428684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$8A72611A-648A-4621-98BF-4A400EF58996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2e5a5b964e58a4c1b445c047d7344e912592d3d","datavalue":{"value":{"entity-type":"item","numeric-id":5932702,"id":"Q5932702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$CE4CFF4B-7BD9-40D4-A45B-478961B4DE1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$1D8BBF2E-0ABA-4905-BA0B-ED97A762F1E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751581187d2b6c441c261ae33faafe5ee0321f46","datavalue":{"value":{"entity-type":"item","numeric-id":1414242,"id":"Q1414242"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$2E06C92F-CA77-4824-BFD4-330C0E721C71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7927952b5fc2972ff92c2aaf07763b9d7722e7a","datavalue":{"value":{"entity-type":"item","numeric-id":2633244,"id":"Q2633244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$B87F73C9-B695-42AB-A1C4-81D84E6A0E9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"072c37fc08b6b305130d3c1b42680a65a72344b3","datavalue":{"value":{"entity-type":"item","numeric-id":4652632,"id":"Q4652632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$68E7F93A-DF7F-4CEE-9D45-415278F8F79C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c837d56e04962823c1d7c934cd015e72d540d8c","datavalue":{"value":{"entity-type":"item","numeric-id":1588908,"id":"Q1588908"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$9D6B9D7D-2BBE-42AD-B0E8-6969912B8BF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e759b8ddc389f8b42bb244f19be1adfe6bb34c7","datavalue":{"value":{"entity-type":"item","numeric-id":5402560,"id":"Q5402560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$C58DB4A4-4BC1-4100-802D-18F250E65E9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ca263fbbb5b5d88e12729380f2dec9703dc4229","datavalue":{"value":{"entity-type":"item","numeric-id":1177910,"id":"Q1177910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$67E3D15B-CF0E-4F38-AE2C-72AE4900B174","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf38d3aafe2ee0b4b6d9fb9a5d5f6717b92fa0ac","datavalue":{"value":{"entity-type":"item","numeric-id":4250183,"id":"Q4250183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$077FEF1F-679E-46BB-AC88-0B8B7E46B92F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8805d0b1cae5fdf1e82c27391003f63fd685cf68","datavalue":{"value":"10.3390/A12010023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2633284$2C9F8DCB-61F2-4F1F-9281-78867BCCED99","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b9ef4dae353a32c6b1e81c11b4344797d89b212","datavalue":{"value":{"entity-type":"item","numeric-id":360493,"id":"Q360493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"523bbc529f6e285f92888ef5bb22d63763e09192","datavalue":{"value":{"amount":"+0.8488689661026001","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":"Q2633284$3446E0DD-257F-415D-B849-DFA7D4635224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8430567af32487215f3e704732c40aa60a8f2730","datavalue":{"value":{"entity-type":"item","numeric-id":2775896,"id":"Q2775896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc1afad9e97a58c75c3a145b96954ad32ae96665","datavalue":{"value":{"amount":"+0.8055400252342224","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":"Q2633284$07A6098E-CA4C-4E02-80EA-22EBD975D872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e0d06e78fc5e55c651eca3ed90808e97b0832ce","datavalue":{"value":{"entity-type":"item","numeric-id":5315378,"id":"Q5315378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17ecfa5c50151652a0536a55d0c4b4d2f408c3f5","datavalue":{"value":{"amount":"+0.8033857345581055","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":"Q2633284$A17A766D-EFAD-4B5A-B187-28D0FB54D8B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30ec2bbcb7fb545385a7536da1c461205cf11dda","datavalue":{"value":{"entity-type":"item","numeric-id":5955469,"id":"Q5955469"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d3cd2a994a53288452853783ff3e67c35bbddae","datavalue":{"value":{"amount":"+0.789238691329956","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":"Q2633284$93594E5F-A440-4ACF-8D66-87385F32321B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a082ed8b2c92c4ce2be65d8f24849d0d35d99d42","datavalue":{"value":{"entity-type":"item","numeric-id":1928521,"id":"Q1928521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cbcb94d412734f956a78bd6aa8890a511a38ed4","datavalue":{"value":{"amount":"+0.7872679233551025","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":"Q2633284$8111161E-0B66-403D-BBD2-6BD6D82045CC","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2633284$216E2DC7-2706-4618-BA3D-FF38F9F89510","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2633284","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2633284"}}}}}