{"entities":{"Q1894355":{"pageid":1905097,"ns":120,"title":"Item:Q1894355","lastrevid":47334214,"modified":"2026-01-01T10:06:35Z","type":"item","id":"Q1894355","labels":{"en":{"language":"en","value":"A new approach to solving three combinatorial enumeration problems on planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 777818"}},"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":"Q1894355$1A9BCA9A-CDD4-42F8-AABB-C34A4E2D2D97","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c4919caeaf084c6cd7e735c5f82d27450d502e1c","datavalue":{"value":{"text":"A new approach to solving three combinatorial enumeration problems on planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1894355$CF154923-F1FD-4C6A-9F7F-F3FC84F10ED0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d0eeffe6cfae67ccdfd9272394a02df036e38015","datavalue":{"value":"0833.05043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894355$B15DDB48-8E86-4890-AC33-B393C953BEAD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"07788ad0f4b68a6aa0d4a05f54c8ead24b69d00b","datavalue":{"value":"10.1016/0166-218X(95)E0111-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894355$0FCED02A-9997-4BC6-B4FC-570B96233B94","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bbbdc3381c094a1abe2cf60ed445a4984b25837b","datavalue":{"value":{"entity-type":"item","numeric-id":168193,"id":"Q168193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$1CA9E9AE-63E6-40C9-89CC-596A8038FADF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ff4ba1aa663765d237e84b0e391fae178ff94609","datavalue":{"value":{"entity-type":"item","numeric-id":1116347,"id":"Q1116347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$46C6FAA6-D6A2-4A0E-B35A-616E4833EA41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"00965660cfd4395683a2a338f67e7ff433027b46","datavalue":{"value":{"entity-type":"item","numeric-id":234402,"id":"Q234402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$5EE48347-515A-4807-88EC-4A52D75FD7BE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$3409BC42-630F-4354-9746-A90D6CC2A693","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3da5740e8a0078651a07b58d85e873b362b3e452","datavalue":{"value":{"time":"+1996-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1894355$7BF4A0E7-58A5-454C-929E-943955B1FC95","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7388261879cc6908fe9c1255edf40d52b8c4199f","datavalue":{"value":"The authors consider six graph transformations: loop deletion, pendant edge deletion, parallel reduction, series reduction, \\(Y\\)-\\(\\Delta\\) transformation and \\(\\Delta\\)-\\(Y\\) transformation. A graph \\(G\\) is said to be \\(\\Delta Y\\Delta\\)-reducible if it can be reduced to a single edge by repeated applications of these transformations, in any sequence. Planar graphs are known to be \\(\\Delta Y\\Delta\\)-reducible; but so is the graph \\(K_{3, 3}\\). The class of \\(\\Delta Y\\Delta\\)-reducible graphs has not been characterized. \\textit{T. A. Feo} and \\textit{J. S. Provan} [Delta-wye transformations and the efficient reduction of two-terminal planar graphs, Oper. Res. 41, No. 3, 572-582 (1993; Zbl 0784.90095)] have obtained an \\(O(n^2)\\) algorithm to reduce a planar graph to an edge.   In this paper the authors present a \\(\\Delta\\)-\\(Y\\) reduction technique to solve combinatorial problems on planar graphs. The basic strategy is to associate a weight with each edge of the graph and express the combinatorial object to be evaluated as a function of these weights and study the effect of each of the six elementary transformations on this expression. Then, using the Feo-Provan algorithm, one has an \\(O(n^2)\\) algorithm to evaluate the expression. Complete details are given for three combinatorial problems: finding the number of spanning trees, the number of perfect matchings and evaluating the Ising partition function of a planar graph. The authors however observe that there are \\(O(n^{1.5})\\) algorithms for these problems using evaluation of determinants.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894355$A0C25DED-DAFC-49A8-8378-6DB8AE646A0E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894355$938E4732-C540-4E22-83C8-66C3ADD03B9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894355$AC0F260F-0A18-4BAB-A8E1-B7EBA9CD54CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894355$F361B03F-A2EE-4540-B3FB-88B3E24FB41F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894355$C0C21354-0FFD-46C9-BDE7-EB6436185356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"239a4a174af03c82b61364f762873d53ef0a37ef","datavalue":{"value":"05C90","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894355$9C09194C-2F6D-40C6-8266-D9556901A5F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894355$E62C3491-574A-49B8-8514-91ED0A5B8C60","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b2d3e1c77371c7dbb2e0cb2ccfbc33c7186e5eb5","datavalue":{"value":"777818","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894355$F08D62ED-77A0-4328-A9C2-A36C39C9C3C3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4f79575c9f7e6c31d23deee24be1ebd6063ad09","datavalue":{"value":"delta-wye graph reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894355$AC7F7F8E-70FD-4430-B357-E4E4D785D2D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a91fd41af6d989c2540a8aa35062b12cfa26c30","datavalue":{"value":"graph transformations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894355$6AEB01D1-16E6-47F3-A4C8-5A598CB1374B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894355$48AB0A4A-8E1F-4DF1-8A0A-9FE59A78A463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894355$147F6A0A-D4CD-40F5-866A-47CF96E64EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b589bf7cbbec414fc701694cc759d8ee0fa05aa4","datavalue":{"value":"weight","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894355$2E8AFFAC-1053-43D4-B6FD-51761E6A3077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1f1861aeda754af488fa73a95b33262d80f4ef5","datavalue":{"value":"number of spanning trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894355$9346C7AC-1494-497A-A0F0-5ED24EBF8639","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"64543c9299bc42c81f3d499c1684150e8404b4af","datavalue":{"value":"number of perfect matchings","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894355$7104F685-F99B-4B7D-9611-D53F56E092D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"061676ab5ab7e97e9f90bdd52f9956ec04e6dd9c","datavalue":{"value":"Ising partition function","type":"string"},"datatype":"string"},"type":"statement","id":"Q1894355$E94BDB4F-6940-4161-B7CD-C61EDA09865E","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":"Q1894355$49C34F09-77A4-461E-9156-9F6DFCF5DAFE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d0bab8d4aa9a79789c4f8631ee79af28637b14","datavalue":{"value":{"entity-type":"item","numeric-id":3266137,"id":"Q3266137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$08FE54AE-4546-46F4-98EB-90F4FCB3BAAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8ab8f2d16c26bc42979e9ef1f9de093f5ccfcc3","datavalue":{"value":{"entity-type":"item","numeric-id":3324796,"id":"Q3324796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$1BE2EA60-666A-400F-8EC5-7946AB685651","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2d5fae29fce4e1471763763841f1668768a93c2","datavalue":{"value":{"entity-type":"item","numeric-id":4198785,"id":"Q4198785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$949E645A-7CF3-4AD0-96EC-7C4DEEDBC9DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef8984b87eaf8e8e64ef599995706f1cf453c35f","datavalue":{"value":{"entity-type":"item","numeric-id":4345594,"id":"Q4345594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$EBD601CD-DCC5-4CE3-B5C5-F055340D5309","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"552c434c142b1241d46d7888ab9d02b4cb9bbfe8","datavalue":{"value":{"entity-type":"item","numeric-id":916681,"id":"Q916681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$C08E6C45-9642-489E-AE35-00DFED8342F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2807a41410595e132197f1ca423f283fef377de","datavalue":{"value":{"entity-type":"item","numeric-id":5528477,"id":"Q5528477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$4D251839-B731-4FAA-84D6-AE767F3029E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6deae6afa48d255973a5bbebca0a15254c83adaf","datavalue":{"value":{"entity-type":"item","numeric-id":4202458,"id":"Q4202458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$323F4609-7D7C-45B3-A674-893360DBD902","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0a50f5e77fdb62ea63f576b687065b56a4937ac6","datavalue":{"value":{"entity-type":"item","numeric-id":5109169,"id":"Q5109169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$C7CE599F-CB68-4CA9-9844-A7C4D27C70E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae9262828d4c17bef03f5c77c7fc2ebb36bcbe9c","datavalue":{"value":{"entity-type":"item","numeric-id":3142597,"id":"Q3142597"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$C4927162-C6DA-4925-A858-A416E31102F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7cbdd4cf597b5efaf84d98e3a02b2ec5b678a450","datavalue":{"value":{"entity-type":"item","numeric-id":5605168,"id":"Q5605168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$87BEC918-852F-487B-9CE6-3339A1994E17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f3b8fc016d02c7cba725e987893d982bac062e7","datavalue":{"value":{"entity-type":"item","numeric-id":5334714,"id":"Q5334714"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$AFC682E4-9342-4956-8779-CD86758F6ECE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6141476b65d14923fb002fbcd5da8a63dbb0016","datavalue":{"value":{"entity-type":"item","numeric-id":3875202,"id":"Q3875202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$A7A2CB8A-7790-465A-AB78-23DDE6A76D0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"20560673347fa07753fe40599896f4c6b70ef341","datavalue":{"value":{"entity-type":"item","numeric-id":1088987,"id":"Q1088987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$CD652CE4-D2EE-41C7-A304-FCFA5DF968EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e43df450aac3d7ee061084bbd64386313cf3c32","datavalue":{"value":{"entity-type":"item","numeric-id":3832586,"id":"Q3832586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$75F66099-ACAD-4286-B861-C87292E7DCBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fcfe987d8cbbd43f7b7238b024d7a85de33a069","datavalue":{"value":{"entity-type":"item","numeric-id":3936212,"id":"Q3936212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$8F562D45-1F62-494D-88A7-593DE248D0CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76d17cdc84d5a7c88fde84de7f32f71667e04184","datavalue":{"value":{"entity-type":"item","numeric-id":5470709,"id":"Q5470709"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1894355$484302D1-C9E2-4380-B440-A1A587EB0608","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bd2dd31d14d704513d3f57f01a3be365d15f2f90","datavalue":{"value":"https://doi.org/10.1016/0166-218x(95)e0111-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1894355$2FA6E6F9-4C3B-422E-8B0F-DDFB9237EDDF","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4d499410260483ab5eb81e93b9703985c26b4b64","datavalue":{"value":"W1995138470","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1894355$61A77D27-36B3-4E5F-8B3F-85EF6D612F49","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"67cc60c1493a17e8678ea5d1bf5fc58047d6ad55","datavalue":{"value":{"entity-type":"item","numeric-id":4202458,"id":"Q4202458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"68fd918407ae71367f162fd12c839041563fac21","datavalue":{"value":{"amount":"+0.8085912466049194","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":"Q1894355$CCA93951-0F25-4230-9C0B-EAF9FE06555A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c36b1b50432f66d648b0ce1b469c96a9288450fd","datavalue":{"value":{"entity-type":"item","numeric-id":2413161,"id":"Q2413161"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dbfd1269dcbad0c88381576671a21394cf7350fe","datavalue":{"value":{"amount":"+0.8082722425460815","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":"Q1894355$10220DBF-78CB-445A-9441-20DE15EFA614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e2c590ea352426a74d708f6ec43b639658a60b8","datavalue":{"value":{"entity-type":"item","numeric-id":916681,"id":"Q916681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d98ab181baa7e7d7dffd08ea507d7ff5327bc3a1","datavalue":{"value":{"amount":"+0.8068509697914124","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":"Q1894355$AF61487F-C0CD-424E-B2B0-C06212F44B6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba302d2b8070627836fd0e8e26b9da3cb8e72ac7","datavalue":{"value":{"entity-type":"item","numeric-id":4430873,"id":"Q4430873"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"84502bd2b4aad03112effce9f239c702be84acca","datavalue":{"value":{"amount":"+0.80474853515625","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":"Q1894355$F6B587E4-1238-4F47-978E-8C8FA63C4C4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"990bef0f1622a5990c6000bc94203840aa06d04d","datavalue":{"value":{"entity-type":"item","numeric-id":3832586,"id":"Q3832586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"063d76de1bbf7d1d35e60e867c23afc048f503be","datavalue":{"value":{"amount":"+0.7998343706130981","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":"Q1894355$DED242F2-0439-4DC2-88B7-25B77F619B58","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1894355","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1894355"}}}}}