{"entities":{"Q2366013":{"pageid":2376756,"ns":120,"title":"Item:Q2366013","lastrevid":46351800,"modified":"2025-12-24T15:10:54Z","type":"item","id":"Q2366013","labels":{"en":{"language":"en","value":"Optimal decomposition by clique separators"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 223108"}},"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":"Q2366013$E5257CD1-2A3B-4CC6-B2FC-F4C785B1A4B7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1b73665ef9343fa377b850352f600e8c25d7c9c4","datavalue":{"value":{"text":"Optimal decomposition by clique separators","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2366013$871676D3-861C-40B8-8216-2A12CEAEA974","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ebb77cf6bb47d761a772ae373f2e71187dc214ad","datavalue":{"value":"0793.05128","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366013$B9690EDC-258E-4B2C-9222-42517DF077D7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dace94b42028176650678e12c54aa7615260624e","datavalue":{"value":"10.1016/0012-365X(93)90510-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366013$B3EE4A87-2D9A-4764-B9E0-8676262F6863","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"eb6707a6db8009f0c00b6fee16e6e040a1b6bd69","datavalue":{"value":{"entity-type":"item","numeric-id":2366012,"id":"Q2366012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$13BFE7A8-CF02-4EFF-B4A4-586AAD87FCE1","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":"Q2366013$DEDE04DC-C976-4AB9-88A8-6BA6283786CD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be4381b75afe2df0dbe37cd1a66e006418c0c5aa","datavalue":{"value":{"time":"+1993-06-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2366013$198A95B8-B36F-45A7-90BC-999D7999CF38","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"15621cc5dbd71ae699c41a30b02c042c8cc063da","datavalue":{"value":"Decompositions of graphs by means of clique separators have been studied by \\textit{R. E. Tarjan} [Discrete Math. 55, 221-232 (1985; Zbl 0572.05039)] and others, and have many applications. These decompositions are not generally unique. The author introduces a particular kind of decomposition by clique separators which does result in a unique set of final graphs---these being the maximal subgraphs themselves free of clique separators. He also modifies the algorithm of Tarjan to produce this special decomposition, in time \\(O(mn)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366013$F33AF062-5A16-448B-9D0F-82B2F1ABC4E7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366013$D696D9AC-0DF2-4518-8400-1E24FD4AC7E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"239a4a174af03c82b61364f762873d53ef0a37ef","datavalue":{"value":"05C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366013$1CDA16A8-2090-43AD-94EB-366FDA9DABB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366013$E9DF41AE-37A0-4477-8260-C198CE306115","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4945d7bea1630fa2f5f033c126d078f083d9868e","datavalue":{"value":"223108","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366013$07D3F609-871C-42B2-BD45-43B2C33429AC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca169439c93bd6a73d76298d8d7ff8b930b865d7","datavalue":{"value":"prime subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366013$C173939F-76EE-4C69-950B-C169430D3F65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f567752019ed0986514776035227dcceb04b780","datavalue":{"value":"clique separators","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366013$8D3F8F05-39FD-4362-AA61-70D71D9948B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d65d96e26ba7f502206a0841e88ddfd329fc1d64","datavalue":{"value":"decompositions","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366013$988C5712-F33B-408A-A421-E700B77AA539","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cc7e193006699e29b5b5a77a1be6eeba002bc504","datavalue":{"value":{"entity-type":"item","numeric-id":338573,"id":"Q338573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$C0E0890F-6681-4664-92A9-2033CD27EEAF","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":"Q2366013$6118A063-6EBD-4F53-B1AC-DF03571B3355","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"371022b650cc13945ab0e0a275daaabc38cde92a","datavalue":{"value":{"entity-type":"item","numeric-id":4064868,"id":"Q4064868"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$FD2BA0D2-D827-4471-B9A5-3E51FA4514D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a08cfcc5870263a5c9ca63fbdf30de9c21f5aec","datavalue":{"value":{"entity-type":"item","numeric-id":3026382,"id":"Q3026382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$7ACD379C-EBB4-4D87-A533-752CD13BC0F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6e19178c31d2525d54646479d5a1544fae3568b2","datavalue":{"value":{"entity-type":"item","numeric-id":1144875,"id":"Q1144875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$182A28E3-04B2-4B09-9FF6-EFB5D1AC1731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a0aa613ca4bd0ec420e7af9ec54e31ed24712e0e","datavalue":{"value":{"entity-type":"item","numeric-id":1068851,"id":"Q1068851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$A2FFD8E8-AE3F-4D60-BF5B-4620A24CDD51","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55d8af290a6b15b48f823117e3ff770098e89632","datavalue":{"value":{"entity-type":"item","numeric-id":1118617,"id":"Q1118617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$4B3497A5-28A9-4174-B895-51634384DB0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"feeda177033aefb91b710e1d67c7f3f979071c88","datavalue":{"value":{"entity-type":"item","numeric-id":2641316,"id":"Q2641316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$40C706FE-BA20-47D8-9A09-03E45B09D20F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"996e29f5273a9b2b00c64e929abf15e49bbb4a98","datavalue":{"value":{"entity-type":"item","numeric-id":2641317,"id":"Q2641317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$4FB0A4AF-C7A4-43F2-B453-2245967C4517","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c1f77c67270a1e87cb7fb47fa6ea39fa4db83bb","datavalue":{"value":{"entity-type":"item","numeric-id":750465,"id":"Q750465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$B6BE825A-4D0C-425A-8859-14B0D68F70D6","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":"Q2366013$69772EC4-7C38-42D6-A3CF-ECF46CCEFD7F","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":"Q2366013$D20BA3E8-C21B-4BC0-B909-20667B5E8232","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e80f4c5fd86589d82d9c08f642bd4f0798ef35b","datavalue":{"value":{"entity-type":"item","numeric-id":4089657,"id":"Q4089657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$8979EF36-C93E-406D-B02E-6F00236AC034","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b5bf2797e8f3ad0d4f657e08f15b3530ad0818e3","datavalue":{"value":{"entity-type":"item","numeric-id":2393913,"id":"Q2393913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$DBACDB82-95C5-41A2-A1BA-7ED6E916F272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c7150c1a02cf9527ec8f2535d125ca07c07feca","datavalue":{"value":{"entity-type":"item","numeric-id":3315548,"id":"Q3315548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$86587357-A25F-44AA-A864-FEE26BAC3958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"527b23cde5f027680452725e3626f6f74e36aa85","datavalue":{"value":{"entity-type":"item","numeric-id":1118943,"id":"Q1118943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$41B9AA9A-14B7-4ACE-A27A-3850E9D03794","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3709cb0f951026908c2620776c252b5ab05d3620","datavalue":{"value":{"entity-type":"item","numeric-id":3834094,"id":"Q3834094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$932F19EA-F53C-477B-8086-F3A304305CED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85edc49e2762f78197ca674de99175269ad0218d","datavalue":{"value":{"entity-type":"item","numeric-id":3290351,"id":"Q3290351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$7D6045AF-5D86-4190-85F4-72BA0535BA87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"710ce3bf2b2ba810c11f400f4025926e4633fed1","datavalue":{"value":{"entity-type":"item","numeric-id":4124208,"id":"Q4124208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$251A896E-F699-4580-B968-32D258326C4D","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":"Q2366013$38C2013C-3282-4A52-9628-8F6C6FA72B2F","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":"Q2366013$5912F4C2-4F33-420A-BF83-A7AEB6649D18","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":"Q2366013$6FF3CE6F-D291-4A0A-92E4-A6070BC8ACA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39c83322ec89a0879c019f012ce18dfec20bc796","datavalue":{"value":{"entity-type":"item","numeric-id":1062072,"id":"Q1062072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$5CA64979-8298-4D65-B3B3-AAAA8B8A2E98","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bba15cf4a9d2c986ffe8184ac3a6d051fff29cb","datavalue":{"value":{"entity-type":"item","numeric-id":3335007,"id":"Q3335007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$FE059AC2-E329-4FA4-8354-4F0FEBCC0FE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc36d733f119bc4d42ab929761edea421cb50305","datavalue":{"value":{"entity-type":"item","numeric-id":5600508,"id":"Q5600508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$759F9511-922B-49FB-9536-2861860CBAC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52413575dffac399ec5e1a273ebc922ef8bf6ea1","datavalue":{"value":{"entity-type":"item","numeric-id":1131647,"id":"Q1131647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366013$9361684C-DD04-4F14-8D0B-78E06067EBFA","rank":"normal"}],"P1643":[{"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":"903979ac31d5e1cbf60b1178c3e3b637d6c69964","datavalue":{"value":{"amount":"+0.8911771178245544","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":"Q2366013$96FA1C2C-4163-43CF-86CC-A44D16C401CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5a4a159364c0d9b9e723ac84540db6f5d2654b5","datavalue":{"value":{"entity-type":"item","numeric-id":1062072,"id":"Q1062072"},"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":"Q2366013$BF0F575A-FE4E-4459-8921-8D4CB20F24D3","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":"ce9988af7e9d25478d54cf9f9f7d8abd629777e5","datavalue":{"value":{"amount":"+0.872963547706604","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":"Q2366013$D981C763-6C04-4F20-AF3B-6EB3523B3B66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc4ae2e7fe25aba551afed62a8b88e3ba6dc24cc","datavalue":{"value":{"entity-type":"item","numeric-id":2918475,"id":"Q2918475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e54f9ac56c0deb3aea368be62fcad0dca65ea2dd","datavalue":{"value":{"amount":"+0.862517237663269","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":"Q2366013$1085426C-71F9-4771-87A1-B293DCBAD765","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":"e87b2031dc9173d34350222e0c32f92f71c0ad85","datavalue":{"value":{"amount":"+0.8414932489395142","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":"Q2366013$A342D31F-302C-4B6A-BBF5-340AFDB8A070","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2366013","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2366013"}}}}}