{"entities":{"Q1356762":{"pageid":1367501,"ns":120,"title":"Item:Q1356762","lastrevid":68541906,"modified":"2026-04-13T00:26:26Z","type":"item","id":"Q1356762","labels":{"en":{"language":"en","value":"Splitting trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1019111"}},"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":"Q1356762$E8A11E69-860D-4E80-9A9D-CD8B31B28447","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3b2d9b0c31ea86551fa4052c85683e63386867b0","datavalue":{"value":{"text":"Splitting trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1356762$587E8A7E-773E-4F03-8979-C8974CF1A34F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e3a996fe0ddb352530167fef88c2b2f47842cbf1","datavalue":{"value":"0873.05036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356762$E1049B12-241F-4E17-984F-0F28FBB5C411","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"54431e1f7d2cb0fec9df22af646e953cab02d662","datavalue":{"value":"10.1016/S0012-365X(96)00187-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356762$029807B0-C050-4DDD-834B-AD4EBF3D1814","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7bf47db66b00e4c421ce1e7ba44bc0c7e860c19b","datavalue":{"value":{"entity-type":"item","numeric-id":190032,"id":"Q190032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356762$8541A06B-B88C-4832-9A6A-682D99D02EBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b12b55279dad8b1bdd626f07e2c7fa2214a73b4a","datavalue":{"value":{"entity-type":"item","numeric-id":1356761,"id":"Q1356761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356762$AFA3C4A5-0572-4CB9-973F-BCF5C948AB11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4249c9a7a0b14df0599e70315ca2a040457d857c","datavalue":{"value":{"entity-type":"item","numeric-id":260023,"id":"Q260023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356762$1DD82C76-5B88-4343-8020-75FD8378A1AA","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":"Q1356762$1C08B96E-BBA4-4F7E-9878-059F92AA5F1A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c751138a14146358143f657cc3ec27365cbcfe5e","datavalue":{"value":{"time":"+1997-10-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1356762$82FB52DA-56FF-4BDC-B7AA-C8D79F1A118A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e98a81552e340b60d39c215a80f64e0583e48834","datavalue":{"value":"This paper considers the problem to find in a graph \\(G=(V,E)\\) a coloring of \\(x\\) vertices with the color white and \\(y\\) vertices with the color black, such that no white vertex is adjacent to a black vertex (and each vertex receives at most one color). Such a coloring is called a black-and-white coloring; \\(x\\) and \\(y\\) are given numbers. The paper considers the problem for trees. An \\(O(n^3)\\) algorithm for the problem is given, based on dynamic programming. With the help of two new notions, the splitting number, and the connected splitting number, necessary conditions for the existence of a black-and-white coloring with the desired number of black and white vertices are obtained. The conditions can be checked in \\(O(n \\log n)\\), and \\(O(n)\\) time, respectively; if one of them holds, the desired black-and-white coloring can be made in linear time. The splitting number is the minimum number of successive forest splittings which lead to the deletion of all edges of the tree, where a forest splitting consists of taking a chain in each of the non-trivial trees in the forest and removing all edges of the chain and disconnecting one from the other edges incident with the chain. The connected splitting number is defined similarly, but now every chain (except that of the first split) must intersect a chain used in an earlier split.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356762$77342CE6-7D39-4AA4-A829-430EEF881537","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356762$3EBA9FE0-6085-498B-8761-9696195C85F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356762$07C1DF14-C155-4D50-BA73-D9DEA20DB712","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356762$174CF2E2-2464-4BD4-8C9A-03E0D76F83EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356762$C8B7C9D9-97C8-4120-9D35-D1B0409182CF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e3f9d88228f92f4717ef9389723643f8623b5a5e","datavalue":{"value":"1019111","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356762$856B5554-E5D9-4C0E-8675-F14C5FC2A4DD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356762$68B51CCE-DA55-48F0-BECC-80452F9C13B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1f0c8674888e5630c81bafa4262c3939ebbd8a3","datavalue":{"value":"splitting trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356762$C6CD8E33-B586-4920-B576-6A170E0C4A7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"822e0eea0239cdcf5b40ce45c22e29d6ffc5e0e5","datavalue":{"value":"black-and-white coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356762$0CD3E569-8F81-46A0-AC0C-37F205F5D988","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356762$DCF11D8B-8438-44A3-8CD0-A20AF021D632","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9b43ae0f190acb8d132b00fab08bb35283981fe","datavalue":{"value":"chain","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356762$87B249DB-524F-4CFE-8418-D49856F40EFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1356762$309288FD-7226-4B34-92C7-54D3597E4439","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eea1ea35de576c62b8101835521aa928ecd629a1","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1356762$29A37106-0954-4CDE-BF57-FAC71FC2681C","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":"Q1356762$89B0EB67-5DB4-47FC-8AAE-EBBA34501C48","rank":"normal"}],"P223":[{"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":"Q1356762$DC5D0ECE-E1D0-42BC-8FD4-A703F51E3CED","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":"Q1356762$070EE231-CA0A-4A26-9A0A-6E4ECA064434","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4efb99f597b7eee364e907459984123813094fbb","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(96)00187-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1356762$9AF126FF-8DDD-4A17-B67A-9D3DC774703F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b3c4d24a118dd0e9dcdac37f13f02205032b6683","datavalue":{"value":"W4212994261","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1356762$9CD6E51E-1414-422C-8E71-5B0802933825","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3478bf8cc736a88e07da6d4d6ceed4c16c981c78","datavalue":{"value":{"entity-type":"item","numeric-id":3184607,"id":"Q3184607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"458dcc41a65734f1a33d558a7856487da1d8030b","datavalue":{"value":{"amount":"+0.859261691570282","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":"Q1356762$798AE234-9FF7-4CDA-ACBC-06772531B40A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cec80c53989f2b6b4d5c6f4f35221de7dbe095af","datavalue":{"value":{"entity-type":"item","numeric-id":3104270,"id":"Q3104270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28776cc68c6786efff9b3e3096b13ba8ef80937c","datavalue":{"value":{"amount":"+0.8332924842834473","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":"Q1356762$6A3FFAAD-5B18-4158-86B9-AC72CB8BE4D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eda8565209178cb60581d54706cd6a8aad372a66","datavalue":{"value":{"entity-type":"item","numeric-id":2445872,"id":"Q2445872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"facadd16715660ac8fdcff8e4caf950fd808f903","datavalue":{"value":{"amount":"+0.7834773063659668","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":"Q1356762$EF213223-928F-4294-A246-A7D4BEBFE7AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44cfa5f4527d7349c5ed56adaf5607afe1ad2785","datavalue":{"value":{"entity-type":"item","numeric-id":2744375,"id":"Q2744375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e322b0aa3ddd4ba2ecf59c56ef54982ccc4bf12","datavalue":{"value":{"amount":"+0.7741115689277649","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":"Q1356762$12B11662-19AF-42FD-96C7-04902315764A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8f58166c0d88f8e343e57bee4452da1f32a88ad2","datavalue":{"value":{"entity-type":"item","numeric-id":2898008,"id":"Q2898008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"670cb246df8e8df9315b32fa79ae1a3a59458c56","datavalue":{"value":{"amount":"+0.7736043930053711","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":"Q1356762$E368F0E1-655F-41FE-8826-BFE8E347FC04","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Splitting trees","badges":[]}}}}}