{"entities":{"Q1086244":{"pageid":1096996,"ns":120,"title":"Item:Q1086244","lastrevid":49011346,"modified":"2026-01-06T11:38:31Z","type":"item","id":"Q1086244","labels":{"en":{"language":"en","value":"Finding the two-core of a tree"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3983183"}},"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":"Q1086244$69643405-F4A5-4924-8A2F-5B2F6C3DAA0F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"27210fee7bd99931bfb375c6b9b6ad9a6d57cc9f","datavalue":{"value":{"text":"Finding the two-core of a tree","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1086244$C6277620-E8C8-497B-86CB-747E7051E917","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"31a4faff587cf33630afe2cd90d74d03ae379f89","datavalue":{"value":"0608.05026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086244$AD56BF5E-078C-45D9-A167-8154C3B638FF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b539d86dac34a646aceaa10c0c68ac4ef642dc88","datavalue":{"value":"10.1016/S0166-218X(85)80002-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086244$7BFDE23A-A705-43EB-94E1-A9DCC28E2718","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5cd2c7be0afdf2927622c7cd78b852044b59e59","datavalue":{"value":{"entity-type":"item","numeric-id":686518,"id":"Q686518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086244$63C7A671-42B8-4CDD-93F0-E326A50D0573","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"526220134f5947b7febab96d61df622608889cb7","datavalue":{"value":{"entity-type":"item","numeric-id":686519,"id":"Q686519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086244$230ECD9D-D0E5-41BE-BB8C-9785C662171A","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":"Q1086244$70EEE347-3536-4534-B749-940F019CF8ED","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":"Q1086244$B1602B3D-9764-4837-AF1B-FF0ADAC811FA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3006546f7ec10275b2698e664bcc83fa5f925524","datavalue":{"value":"The core of a graph was defined by \\textit{C. A. Morgan} and \\textit{P. J. Slater} [A linear algorithm for the core of a tree, J. Algorithms 1, 247- 258 (1980; Zbl 0454.68067)] to be a path minimizing the sum of the distances from all the vertices of the graph to the (nearest vertex of the) path. Finding the core of a general graph is NP-hard by a trivial reduction from the hamiltonian path problem which is also NP-hard [\\textit{M. R. Garey} and \\textit{D. S. Johnson}, Computers and intractibility, A guide to the theory of NP completeness (1979; Zbl 0411.68039)]; however, for trees a linear algorithm was presented in the paper of Morgan and Slater (loc. cit.).    In the paper under review, a 2-core of a graph is defined to be a set of two disjoint paths minimizing the sum of the distances from all the vertices of the graph to the (nearest vertex in the union of the) two paths. Finding the 2-core of a general graph is also NP-hard [Garey and Johnson (loc. cit.), problem GT 13]; for trees this paper presents a simple quadratic algorithm and a more sophisticated algorithm which runs in O(nd) time on an n-vertex tree of diameter d. The O(nd) algorithm is an improvement over the \\(O(n^ 2)\\) one in the average case since the average diameter of a tree in O(\\(\\sqrt{n})\\) [\\textit{A. Renyi} and \\textit{S. Szekeres}, On the height of trees, J. Aust. Math. Soc. 7, 497-507 (1967; Zbl 0153.258)]. Another O(nd) algorithm is presented for finding a set of two intersecting paths in a tree with the same minimizing property.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1086244$F71C1439-271A-43BC-AFDE-5EB33EA68577","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086244$D3171680-DA9B-4BDC-872C-AC168ACF6227","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086244$A118BEA2-FAA5-4455-9418-DAD568C44A96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086244$61CF1F37-6FB2-499D-A167-12877F43F22E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086244$61C235CB-3864-4434-BC2E-F8598DE4077B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086244$ED7D6801-6B17-47FF-8CB6-603537D7AAD7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"20e7ff3978d70325f6f732bea5764f626056de6d","datavalue":{"value":"3983183","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086244$7408A0FD-6548-42BE-B753-7EF585E2F39A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bff5beea16a8814220a01f4d99e4a37715c839c9","datavalue":{"value":"minimum sum of distances","type":"string"},"datatype":"string"},"type":"statement","id":"Q1086244$1054FD20-B28F-4FF6-8F13-F1FDD9C40446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1086244$25E687C4-3E0E-4427-91CE-05F4C91F3C9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c895d3d7df1dc47ab6dc781c79a6862c634ec9f0","datavalue":{"value":"quadratic algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1086244$62FE82E7-B80B-4E90-8C0E-0136D91DD227","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"457b59512685cc959c2dfec1eb05d289a709afaf","datavalue":{"value":{"entity-type":"item","numeric-id":442385,"id":"Q442385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086244$FE770A23-D364-4B5B-B9E7-320025F21423","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":"Q1086244$87E40CF3-2F15-42B4-9185-1D9BAACBA92F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8986161e172d965c546a046b002a91e3baa49d8","datavalue":{"value":{"entity-type":"item","numeric-id":1171885,"id":"Q1171885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086244$8C54AFDE-8220-4255-A778-209F58223B73","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":"Q1086244$2A9ECF9B-E4C8-4884-B6ED-3EDBEC6BEEC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086244$060DE257-EE3B-4C96-8B15-E42844C35CB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a1b3a23bef9ff22b898fb87db53c1229f631a7c","datavalue":{"value":{"entity-type":"item","numeric-id":5735194,"id":"Q5735194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086244$FCF85E4F-997A-4BBC-B7E8-03C3B21270AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc6482fda869c7df0ed32fd6ade8f790a1ff04cc","datavalue":{"value":{"entity-type":"item","numeric-id":5585020,"id":"Q5585020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086244$575A7F27-3F73-4D5B-9F09-58F84A800019","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19ee47c47c223cfb9ec56146022c30ef75f454f0","datavalue":{"value":{"entity-type":"item","numeric-id":3870691,"id":"Q3870691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086244$D57C0260-A8D4-46C4-8F4E-2C2657EE69B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d9cbd6d6903e66fd2a66c23e7cf25785f1d6723","datavalue":{"value":{"entity-type":"item","numeric-id":3902510,"id":"Q3902510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086244$AC3CCA1C-0654-42DB-A274-358DDA39A8A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3029963b02eaad6ed0978fbdaecb8c6bcb64f410","datavalue":{"value":{"entity-type":"item","numeric-id":5534022,"id":"Q5534022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086244$A895C9C5-DB5F-4430-ACB1-55AA75BE1F0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1944ee58d017491e8df2e281260262732ef9eb63","datavalue":{"value":{"entity-type":"item","numeric-id":3922726,"id":"Q3922726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1086244$A961A5B5-DB38-4B1B-ABA6-0FFEB2E7D06A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6d7d3dd5f8c2460b1541bbd3a640f313d7a68785","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(85)80002-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1086244$6A6A03CF-FA99-4B60-A081-F9D6398095C1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"56f632d826cbc80ae1c5681bd0deb8630b1160ea","datavalue":{"value":"W4210342397","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1086244$B59CD153-F6CF-4D74-A44A-195312108F8E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f488c7506af44d8ae09f4d4e3e47800ea7601a0","datavalue":{"value":{"entity-type":"item","numeric-id":4472520,"id":"Q4472520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"57835e802184b60160f3f70583d333afb3ebc962","datavalue":{"value":{"amount":"+0.8999276161193848","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":"Q1086244$A7EA3717-F959-4354-9E31-E88D8E49A0D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e42f32248d65add97a276530684aff8088731a54","datavalue":{"value":{"entity-type":"item","numeric-id":2784511,"id":"Q2784511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2835c9c69cda270e85be3756aaf563a23992a66","datavalue":{"value":{"amount":"+0.898131787776947","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":"Q1086244$DAC366DC-DC5C-4141-A8B1-F410C78E93EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"76dda3c2fc011a1ad4f53d0cbc0537909ab27a67","datavalue":{"value":{"entity-type":"item","numeric-id":3340877,"id":"Q3340877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2835c9c69cda270e85be3756aaf563a23992a66","datavalue":{"value":{"amount":"+0.898131787776947","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":"Q1086244$667C91D5-B565-4894-9031-C7B619A278D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd29bca977e34001b8ce060fa9611b890ab08654","datavalue":{"value":{"entity-type":"item","numeric-id":3141526,"id":"Q3141526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31c62e1ab281b03ab70c01d91893c6a25f47e750","datavalue":{"value":{"amount":"+0.8806735873222351","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":"Q1086244$C0D024EF-6A48-42B7-BA9A-F00155448FA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0d8bc4a7a8876c30a0f1d2be743251693cdab2c","datavalue":{"value":{"entity-type":"item","numeric-id":1935945,"id":"Q1935945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31c62e1ab281b03ab70c01d91893c6a25f47e750","datavalue":{"value":{"amount":"+0.8806735873222351","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":"Q1086244$DAF52346-076E-4151-9820-DFE56CC32F95","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1086244","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1086244"}}}}}