{"entities":{"Q1111390":{"pageid":1122139,"ns":120,"title":"Item:Q1111390","lastrevid":49223935,"modified":"2026-01-06T19:26:43Z","type":"item","id":"Q1111390","labels":{"en":{"language":"en","value":"Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4076647"}},"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":"Q1111390$0D86BACD-D717-48D2-84A3-A1603AD70FA2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"331efd1d0064afccabda03a4aa408e922482c0b0","datavalue":{"value":{"text":"Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111390$D567AF5F-0165-485D-95E0-F67AF4AA66C8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"6f508737dda8a56fa00121e6ebd2200a2f4c1aba","datavalue":{"value":"0658.68079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111390$4C2D2D76-9A0C-42F8-A97E-7CC49DDB6D2A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c3115f2a68e41fcf6c313e15936c113880c0e3a6","datavalue":{"value":"10.1016/0020-0190(88)90178-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111390$81AB7062-63CF-4FBB-823A-E1313BC3328F","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":"Q1111390$086B2441-3235-406C-8EB3-B825BAE6B1F2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1111390$014B53F3-F0EE-49D9-A015-4B4BEB4594B1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a8b6144c90b529a2eb0b2e186b4fed7bafd02cec","datavalue":{"value":"\\textit{J. Naor}, \\textit{M. Naor} and \\textit{A. A. Schaffer} [Proc. 19th Ann. ACM Symp. Theory Comput., 355-364 (1987)] proposed parallel algorithms for several problems on chordal graphs such as computing maximal cliques, a minimum coloring, a perfect elimination scheme and so on. They first solved the problem of computing maximal cliques in \\(O(\\log^ 2 n)\\) time with \\(O(n^{5+\\epsilon})\\) processors and, using this result, they solved all the other problems. We propose another parallel algorithm for maximal cliques which can be executed in \\(O(\\log^ 2 n)\\) time by using only \\(O(n^ 3)\\) processors. This result reduces the processor bound from \\(O(n^{5+\\epsilon})\\) to \\(O(n^ 3)\\) for all the problems solved by Naor et al. Based upon this result we propose another two algorithms for computing a clique tree and minimum coloring which are more efficient than those proposed by Naor et al.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111390$8143AEDA-173F-4392-B61C-D478CA978AEC","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111390$85E7151B-421D-4FB3-A1C2-E340734C1632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111390$DF581502-424B-4404-A617-FD684EB7CAFF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"df3b597000488557c9e16523f7fb32343d1baad5","datavalue":{"value":"4076647","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111390$A5BA37D8-5AD9-4B62-844E-495BCDFDA609","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"77c6f1b09549445d5ec498e4c4bf0d8fc2fe6bbd","datavalue":{"value":"graph separator","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111390$51420E37-EED4-4D14-B799-42049558187D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111390$A45A999A-94C7-4A02-AFF3-C1125F51E1C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"853bd0b31f9734652041500f2e432a6c8df42e70","datavalue":{"value":"chordal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111390$B9DF5F95-A111-447D-9F0F-F6815F16C0BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f115a81543b37fe4640b1c297f0c9115ab3eeff5","datavalue":{"value":"maximal cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111390$9C3D4043-A977-46A3-888C-FBDE752C7F9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b5e5336cab30e039ac622a0d2dff0f49409a421","datavalue":{"value":"minimum coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111390$F545F746-8D1C-40FC-BA3F-D8A31FD34C1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"409fa3c5ea49bf63e4fe42238f5812f87c8b2faf","datavalue":{"value":"clique tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111390$585FFC58-8BAD-455B-A3C1-8D9C7B647636","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c82e19a032ca9256003aa2cc5ca5843bbf680284","datavalue":{"value":{"entity-type":"item","numeric-id":293189,"id":"Q293189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$101F40ED-CF2E-4300-BC7B-8DEBE0DFB5A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"47287d42254c668443f35e7681b0c02cf3b2e14b","datavalue":{"value":{"entity-type":"item","numeric-id":702771,"id":"Q702771"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$D37715E2-B15E-48D1-AC52-55A222F4EB9E","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":"Q1111390$015A3153-F5E9-45D4-81E1-2EB848EE2143","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c4c518768c67a8bf67664051e355371daa105cdb","datavalue":{"value":"https://doi.org/10.1016/0020-0190(88)90178-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1111390$B702A1DD-971C-4099-87E6-453C65B0CF33","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"115c53798c19c76a8ef489d19c65becf9b572775","datavalue":{"value":"W1968285535","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111390$BA9D9173-3C5A-4D7B-9C75-A96694B95A8C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea1e389dfb71f269b8d31b8cd0a0a73c867c2dd8","datavalue":{"value":{"entity-type":"item","numeric-id":801686,"id":"Q801686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$423B8A7E-D047-4A4D-92EC-02C1409D9374","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9348e1c9ad5465f71daa6350b7dddd13e3961e6d","datavalue":{"value":{"entity-type":"item","numeric-id":1098312,"id":"Q1098312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$4F9DDD8C-46EB-4508-BC42-402473212324","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82cec48443acb97048e2cdedb86d0d328426b526","datavalue":{"value":{"entity-type":"item","numeric-id":1846437,"id":"Q1846437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$19D53390-AE06-4CA2-B142-04080BC9754C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b43e3e48b388828a7b8aa17c3f81b7b754c93ecd","datavalue":{"value":{"entity-type":"item","numeric-id":773621,"id":"Q773621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$67835A5C-5924-40D1-9515-22A7BD89960E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"62e08e0780aba8fb3db365e89480e21a54766acc","datavalue":{"value":{"entity-type":"item","numeric-id":1108003,"id":"Q1108003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$B5A45F2D-3CA5-4ABE-A495-4B951E748E6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c74b7954c4e96ea2e676044196dc57d8b06146d","datavalue":{"value":{"entity-type":"item","numeric-id":2395457,"id":"Q2395457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$1B3E4B04-47A4-46C7-970E-BAA0056AD318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e458531dc8f9b4a4f76ca8cb6a5d9d31ac768ee2","datavalue":{"value":{"entity-type":"item","numeric-id":2562090,"id":"Q2562090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$AD0BAEF4-EE8B-4C51-9BEC-4D180CC7E931","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"208d8b2742968ad5d6cb79b1d05ef3d75144d863","datavalue":{"value":{"entity-type":"item","numeric-id":3344230,"id":"Q3344230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$3BCBA80A-3BD3-45E2-934B-B327015929E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$160726FF-4CAD-4305-8F2B-752912EB9D02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00708b4078648865d18948bef9499b484690d96c","datavalue":{"value":{"entity-type":"item","numeric-id":3867197,"id":"Q3867197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$686A5344-F31A-4145-9C8C-328D630C8CDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"560cf79f2da7cba5ae2e5720b94d4db8d7e82ec9","datavalue":{"value":{"entity-type":"item","numeric-id":3219774,"id":"Q3219774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$4484F0A7-ED7D-4530-819E-5573E018700E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b546b29506726197d486ce9c402fd37a52289738","datavalue":{"value":{"entity-type":"item","numeric-id":5683627,"id":"Q5683627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$C616A0FA-C0C6-4970-987E-A05AA9B92897","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a9db4a207e2ab9eef002ed1bcd0688887d186bc","datavalue":{"value":{"entity-type":"item","numeric-id":3957960,"id":"Q3957960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$F4863412-D067-4AE4-80CB-473D8F7B4216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c5477e08259683f4f1214eab272881c214067b5","datavalue":{"value":{"entity-type":"item","numeric-id":3694710,"id":"Q3694710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111390$530E9701-AA4A-4A4A-8E3A-BE000695CD8C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac3393aaec042b8ef507f593067bc774086d2e38","datavalue":{"value":{"entity-type":"item","numeric-id":3825102,"id":"Q3825102"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"239eb33fdb55792a20378d2ee0e271d58c4d5ab5","datavalue":{"value":{"amount":"+0.8760651350021362","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":"Q1111390$F63C2BFE-B399-4042-9ABF-54105D0AEC98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"52fa77354ba3d8550545faba77db2fe81c5e368f","datavalue":{"value":{"entity-type":"item","numeric-id":4895831,"id":"Q4895831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"892775ec6f7939da4274e60de661c1c9f8638044","datavalue":{"value":{"amount":"+0.8751677870750427","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":"Q1111390$ED7E915A-A68C-4DFF-B48B-4AF8862D2044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65e398b4d1a2ff4bf04f038e177060bfe1f8faef","datavalue":{"value":{"entity-type":"item","numeric-id":1262131,"id":"Q1262131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3df1fc57f2cc441eaba374470fc369e3d62bdc1","datavalue":{"value":{"amount":"+0.8364445567131042","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":"Q1111390$61A64411-8699-42CF-B00A-F394481774B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1461130c444387dd226cf060dfc2dbb3a7affc02","datavalue":{"value":{"entity-type":"item","numeric-id":3804207,"id":"Q3804207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91e351de35ef42fa2dc213aaee9bcfad1da6ec88","datavalue":{"value":{"amount":"+0.8227698802947998","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":"Q1111390$7925F4D3-2498-4F3B-AE81-A95DFB4C4542","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8122f298834116847ba9a86970ab248b21dfc0c3","datavalue":{"value":{"entity-type":"item","numeric-id":3806839,"id":"Q3806839"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86d2c0eab70c0ef1e1baf47ab8f9ef06c0c80f73","datavalue":{"value":{"amount":"+0.8163647055625916","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":"Q1111390$AAC67ACA-9A19-4ADF-8EA5-DE732C254FAB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1111390","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1111390"}}}}}