{"entities":{"Q1062072":{"pageid":1072824,"ns":120,"title":"Item:Q1062072","lastrevid":48837379,"modified":"2026-01-05T23:31:54Z","type":"item","id":"Q1062072","labels":{"en":{"language":"en","value":"Decomposition by clique separators"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3912420"}},"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":"Q1062072$B8E02F0D-0E0D-4593-93D3-BF7105BF34AA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4943540a2ddce89063bcec0b102cb77134ca4d49","datavalue":{"value":{"text":"Decomposition by clique separators","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1062072$2E6A6332-A024-46D8-A969-420A99F739AE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ae709407286edeaec4534ed03ab5b98ad49c3739","datavalue":{"value":"0572.05039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062072$80F2D11F-5D37-42F6-9353-137E22BCB5E8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"65a8bb19c0a22ba618e09174b8b718c419861a36","datavalue":{"value":"10.1016/0012-365X(85)90051-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062072$64EFF071-FC5D-4F5C-8E66-7BE595704477","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$E1367BB0-C622-46EC-8411-8530CDDD8465","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1062072$607859CA-B7BC-402B-9E05-0E2DC7192AF4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"283ac1b9b4e2388e2807049cf9900913a5412782","datavalue":{"value":"In this paper the author introduces an interesting theory of decomposition by clique separators which is related to the theory of elimination orderings. The main result is an O(nm)-time algorithm for finding a decomposition of an n-vertex, m-edge graph. The solvability of this algorithm is proved and it is used in application to NP-complete problems. In Section 4 are given the classes of graphs decomposable by clique separators.    \\{Reviewer's remark: It is possible that there is a relation with the results of \\textit{J. E. Hopcroft} and \\textit{R. E. Tarjan} [Isomorphism of planar graphs. Complexity of computer computations, Proc. Sympos. IBM Thomas J. Watson Res. Center, York town Heights N.Y. 1972; 131-152; 187- 212 (1972).\\}","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062072$E9ED6E50-DD53-435D-B2C2-FB84BC54F0F6","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062072$EE819728-DF28-4380-99CB-BA4B8F415A8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062072$A90CAB42-28E5-4600-AE03-DC4308DFFBC5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cf3a9bc770b71a8b5916e6bd697c8cfff6c5710d","datavalue":{"value":"3912420","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062072$A759B3C9-B5B3-4291-9380-E3CFFAFE81E6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f87bc0c01222c5172f3d04d05c84effb63009adf","datavalue":{"value":"decomposition by clique separators","type":"string"},"datatype":"string"},"type":"statement","id":"Q1062072$1616DF10-814C-4AAA-BD27-49F29C009B8B","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"7192058d7ea1009ffb904b641c77a62815d8008a","datavalue":{"value":"Q56335617","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062072$F530708D-699F-4CAC-B725-FEED24779E72","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"065c91f208b67eb2296cd8ea5272c33efd202f25","datavalue":{"value":{"entity-type":"item","numeric-id":598808,"id":"Q598808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$648D2E1E-CED5-4305-B212-3065FC01BD21","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":"Q1062072$9306999A-2FB0-44F1-899A-769FB5FB9830","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$184EAC14-7A2C-4262-AB35-1444F9B838C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88e2c5246172b5aa8717d5936f7b97d7076bc110","datavalue":{"value":{"entity-type":"item","numeric-id":3941433,"id":"Q3941433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$22B053BF-FBD6-4D2F-BD19-87EADE534CA0","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":"Q1062072$583A22D4-52BE-4009-826E-11768E481DDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd8b848f40aaa3f56b8b15df38fbe662aeb1afa","datavalue":{"value":{"entity-type":"item","numeric-id":5516087,"id":"Q5516087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$6021367B-0B0F-4123-B79B-84CD2580502B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cb2ca458acea0e3632727170dcd237e7765fa59","datavalue":{"value":{"entity-type":"item","numeric-id":5514188,"id":"Q5514188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$08066F7A-088E-4DB5-94FE-1B186FB64A71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c406cccfaf0baf112bd503da4f4373902a51376","datavalue":{"value":{"entity-type":"item","numeric-id":4093489,"id":"Q4093489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$7840C760-9639-4161-B091-CCDB7DCD1401","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":"Q1062072$059FE55F-06B3-4CA2-8D78-2438F28481DA","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":"Q1062072$A9BFF1B9-8D62-4631-B087-3AF5C2F1CCAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c33959e8c3fbe7080f98305389592daf8f06321e","datavalue":{"value":{"entity-type":"item","numeric-id":5634016,"id":"Q5634016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$5C9E3399-31FC-4111-A761-B4FEEB92885B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c0194643ef28e9a8173abc6bbf30f54f1d43084","datavalue":{"value":{"entity-type":"item","numeric-id":1246434,"id":"Q1246434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$32A6E641-078F-4B0E-836A-F77332A199F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfac72f7b3c8b555870f83e73f107a945d230f0d","datavalue":{"value":{"entity-type":"item","numeric-id":792348,"id":"Q792348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$66CC1CCF-B726-4B08-AD16-A48012A6D04F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2e498f8f059ec2cdc0575cdc006d5c453bc3e3f","datavalue":{"value":{"entity-type":"item","numeric-id":1060226,"id":"Q1060226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$4F7A361D-1F7B-4CCB-B8A5-90AEBDC78490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e93fcc5f5e8911813f16fcd1e3e08e519d9e013","datavalue":{"value":{"entity-type":"item","numeric-id":4767335,"id":"Q4767335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$001766C1-E5D2-45F7-8764-6889A471449E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$205958FE-D4D5-49C1-A6D8-A371AED296A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2ad7df6fc66261f0adbf0d71d21cd6218acbb91","datavalue":{"value":{"entity-type":"item","numeric-id":4047571,"id":"Q4047571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$BE30B0DE-6B96-4175-A31E-E04774A56AB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ff8a807471958a38eef5720fd27b64677c1d24","datavalue":{"value":{"entity-type":"item","numeric-id":3869371,"id":"Q3869371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$CB7346F2-8280-46E8-B466-3E9771AE9C31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daf1b2c53ee4a6aaa216a1d0505e15485a1f1842","datavalue":{"value":{"entity-type":"item","numeric-id":1243572,"id":"Q1243572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$AD0A4147-6D19-4665-A199-C49E30325376","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a3f4f623c55f4103180bc7ed3e80e030c1afd8b","datavalue":{"value":{"entity-type":"item","numeric-id":2545884,"id":"Q2545884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$6775E158-D8AD-4C98-B162-5CCE4D1FCD79","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":"Q1062072$5517E1B5-8FB4-4760-8AA2-08E82326C5B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8592b19f12bd09556a4de81ad49778d747c4f77b","datavalue":{"value":{"entity-type":"item","numeric-id":4124209,"id":"Q4124209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$8C657A4D-330E-4F39-92DE-01C06E4D936C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4d06e8ffe51c0e0e5032701b55a85074de5383c","datavalue":{"value":{"entity-type":"item","numeric-id":5790769,"id":"Q5790769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$40A88003-228F-4F94-88F7-9C1343934AE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c71680a4ab9e1f4beb0d4c1abad68c079fb9c955","datavalue":{"value":{"entity-type":"item","numeric-id":3945592,"id":"Q3945592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$DA827B5C-8630-45D3-9AF9-5A7330B76239","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a791e6b13200f21127f48f475b5988c15175f95b","datavalue":{"value":{"entity-type":"item","numeric-id":5663889,"id":"Q5663889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$D749A661-C316-43B6-A1EC-239A8A22B65E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67b9b8eafd1b87c89b391a5a966c0dde6e01b96f","datavalue":{"value":{"entity-type":"item","numeric-id":1149784,"id":"Q1149784"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$B998BDC8-6268-4915-AD44-733BDDA9B41F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c20b9c062c65fa50baeb0cadac82aad397e032bf","datavalue":{"value":{"entity-type":"item","numeric-id":3960122,"id":"Q3960122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$DB4CE41B-B4AD-46C3-8499-D8E06274E413","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7f35ad3922723c7d6ad914a9618a7d01da74588","datavalue":{"value":{"entity-type":"item","numeric-id":4731197,"id":"Q4731197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1062072$8F7C0FC6-02B3-46D3-B978-8924F8AAA2EA","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"069ed93515d955dfc433be107c6c95cbc3d382e9","datavalue":{"value":"journals/dm/Tarjan85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1062072$6C2C8ED1-6D44-4461-8150-B9F6D50A1367","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aca81cc779a97f0d7c55070c78bebaa1c425423e","datavalue":{"value":{"entity-type":"item","numeric-id":2366013,"id":"Q2366013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da62fec61cbfd58b3e44febc9a95290217463937","datavalue":{"value":{"amount":"+0.8886458277702332","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":"Q1062072$A9825400-4AF3-4A2E-95C8-2020F3123DDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4065c59a4fe9a3ebc37486e38fe7dac3bfe5edbc","datavalue":{"value":{"entity-type":"item","numeric-id":5492956,"id":"Q5492956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"794dfc7d2346d5e66238aad1a0bc57a2f880c6ef","datavalue":{"value":{"amount":"+0.8886457085609436","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":"Q1062072$C1B8D6B5-41B7-48BE-BF76-625894DB07C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c4f091ed3fa3859284dfb99d560143e1e4b59c3","datavalue":{"value":{"entity-type":"item","numeric-id":4610181,"id":"Q4610181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91540dfe7913dc72db76e2f0842b6506a90387a9","datavalue":{"value":{"amount":"+0.8829887509346008","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":"Q1062072$FA9FA13D-3775-4C74-8AF0-551025922A63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f62c5c2c9327a99032246b845e9b3f15255a7cdd","datavalue":{"value":{"entity-type":"item","numeric-id":465285,"id":"Q465285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7c63aabe3bb9039192f800f4da3e548d0fe5651","datavalue":{"value":{"amount":"+0.8660750389099121","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":"Q1062072$42C438E8-524A-4D13-B1B6-8858B42CC4A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"97c0e308f4a8f3d0d0bc724aeafe9d75c42d4dec","datavalue":{"value":{"entity-type":"item","numeric-id":1662549,"id":"Q1662549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ede717cd1aa411d9d076c49b5ba5996ebce9ec35","datavalue":{"value":{"amount":"+0.8355826139450073","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":"Q1062072$D0DBD305-2D71-4D5B-8BF4-939BFCA4A243","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1062072","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1062072"}}}}}