{"entities":{"Q1805468":{"pageid":1816210,"ns":120,"title":"Item:Q1805468","lastrevid":72994542,"modified":"2026-04-14T09:15:37Z","type":"item","id":"Q1805468","labels":{"en":{"language":"en","value":"The minimum spanning tree problem on a planar graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 756168"}},"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":"Q1805468$89F4E33C-98ED-4672-AC21-EBB922A1E9B0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f8191fb4f3ec9664337a288c39d790d0c1219ef8","datavalue":{"value":{"text":"The minimum spanning tree problem on a planar graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1805468$D7007ECD-C4A1-469E-9C70-B35459E8F09C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"14daf0e423ec83a02cb641dfe1bea64032eebce3","datavalue":{"value":"0823.05024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805468$BE9C6D36-D8ED-4A24-AF3A-29B6D3BA07A8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8a03fc047ab5e5b6df01f38e2a3879ccbc12d03f","datavalue":{"value":"10.1016/0166-218X(94)00095-U","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805468$CCA1ED39-5090-435B-8485-3442147C5A32","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a4823a17a3162b10b1d698265531810e945d9143","datavalue":{"value":{"entity-type":"item","numeric-id":402373,"id":"Q402373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805468$C8D3F459-5A1B-4452-8548-21C6B938624A","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":"Q1805468$8DBCB55F-B92D-40E5-A63F-DFAE485A458F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3250b5ad09e7c3aa70f4d14d28f21a5487cfeb8a","datavalue":{"value":{"time":"+1995-06-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1805468$5A57971B-13B3-41F9-9BFA-CD600B81C0BC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"072e3eb8d01c6e9d2e1216d8e731654d55398436","datavalue":{"value":"A minimum weight spanning tree algorithm for planar graphs with time complexity \\(O(n)\\) is given. The algorithm maintains a pair of a planar graph and its dual graph and breeds both a minimum spanning tree for the original graph and a maximum spanning tree of its dual. The author claims that his algorithm is easy to implement compared to other existing algorithms for the problem which have the same time complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805468$4EF1BA29-9C97-4BCE-827D-20FEDB213090","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805468$3D74727A-E03F-4756-9B36-4695B339E4AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805468$75852E1F-F619-4817-B31F-BCE182AA4751","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805468$7FF4F544-50A3-4AA3-BF9B-DE9D43E73488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805468$8CAE8B05-335E-4BAC-BA32-90EE2A85E468","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"be7396a51e9330878ace99bcd4e1125b4eccc4e5","datavalue":{"value":"756168","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1805468$1C041462-BE65-479D-95B1-38CD8CC56F25","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e949e999655239ac9ec4d9f8c16e1357e2ffe9b0","datavalue":{"value":"graphical algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805468$33BF211D-2755-4B2B-884F-AF53509884D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3065e23cb4d051d6be889edc03bf67315b4d9fcd","datavalue":{"value":"minimum weight spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805468$68AFD42D-324B-4B98-8FE7-32CCD945625C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805468$99B16D72-485A-496F-8F0B-A901D37FE889","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805468$2ABBD28D-C66F-46E3-9C86-89757B15EEB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1805468$18E47EC0-FB10-41F8-9DBA-589E1005FD3B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2499add345269c93c5ed1b650d8b90573cb6b1a8","datavalue":{"value":{"entity-type":"item","numeric-id":242846,"id":"Q242846"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805468$4D38018B-DD66-43EA-A50A-46B483EF54FF","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":"Q1805468$0067A22C-FCBE-46D4-8169-99B9E61C52CE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5f50bb2463f68a38c17b8200f5931261dc0c5e7e","datavalue":{"value":{"entity-type":"item","numeric-id":4132283,"id":"Q4132283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805468$C6D29D1B-C4A0-4489-80B9-29C4C92BADC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805468$3282E1E3-A93C-430B-95C5-B18B64D0A906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6704ccbb4c75ac5e07412c0181b63f464f1b7a0e","datavalue":{"value":{"entity-type":"item","numeric-id":5225293,"id":"Q5225293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805468$3508EBE0-C290-46EF-8D9A-0DCD8F5B2A24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d601b5a73aa3f981ed43e68477a6afb0b2f45837","datavalue":{"value":{"entity-type":"item","numeric-id":1086246,"id":"Q1086246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805468$173798E1-8DBA-4F59-9F8F-900E2F274B55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba838fdee5bc63055b0afae3a6a1506c97a6e142","datavalue":{"value":{"entity-type":"item","numeric-id":4065028,"id":"Q4065028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805468$B5B65EA9-C3E2-45E5-9AF7-ED7A9F008003","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84c35c3c18100f10a76a9ef0d730325b542a65e7","datavalue":{"value":{"entity-type":"item","numeric-id":115238,"id":"Q115238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805468$7B3B724C-1C49-482B-986C-9B4065F6A76F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08736496fad7f1ee1630e83b4f57fe1861c09098","datavalue":{"value":{"entity-type":"item","numeric-id":3048571,"id":"Q3048571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1805468$350FD463-4143-4B84-8743-5EB945991363","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf99ca37380d54c9066538964870d7d20d51047d","datavalue":{"value":{"entity-type":"item","numeric-id":3464472,"id":"Q3464472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4028b924406994446481dbf160e05dedf504382f","datavalue":{"value":{"amount":"+0.847051203250885","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":"Q1805468$123796DA-F363-4B44-B6CB-BF443AC8AE97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f39a99ebcba50ff6da74c6ac578e75368e704ea0","datavalue":{"value":{"entity-type":"item","numeric-id":1391297,"id":"Q1391297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1feec92ced2a8bf6befaff871997f9b9641e4e4a","datavalue":{"value":{"amount":"+0.8407472968101501","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":"Q1805468$D49B39D6-4C24-42F9-94A7-0D95E480D9DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e12f72a443abce876474bdff77ffff3479125f99","datavalue":{"value":{"entity-type":"item","numeric-id":3435477,"id":"Q3435477"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"98f80f4b47a8a5ebd2d7b11f89f8901becca8d06","datavalue":{"value":{"amount":"+0.8310844302177429","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":"Q1805468$C193F5D8-B864-4068-AB5D-966C412FEA3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35bc56fb939e0452ee4f477500b796cc6533f9c3","datavalue":{"value":{"entity-type":"item","numeric-id":5096337,"id":"Q5096337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"091ede7dc2b2ee1db48325947750f4907208559b","datavalue":{"value":{"amount":"+0.8254767656326294","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":"Q1805468$B1BDCB4C-E167-4B00-83CA-694D0CC4354A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6dcebfd63db34412047c1449b356347c38a56feb","datavalue":{"value":{"entity-type":"item","numeric-id":3196633,"id":"Q3196633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73b143b5e976c65e0b1c4394eeaab8b919ba1829","datavalue":{"value":{"amount":"+0.8250167965888977","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":"Q1805468$8C768D43-60FC-4104-A9D5-42CABE79D106","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The minimum spanning tree problem on a planar graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_minimum_spanning_tree_problem_on_a_planar_graph"}}}}}