{"entities":{"Q1579547":{"pageid":1590287,"ns":120,"title":"Item:Q1579547","lastrevid":72241314,"modified":"2026-04-14T03:34:57Z","type":"item","id":"Q1579547","labels":{"en":{"language":"en","value":"Degree-preserving spanning trees in small-degree graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1506817"}},"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":"Q1579547$CA4F1D69-2111-4C9B-9D54-B5AF74680F53","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f601875b6a645289f8969277dce64469f0458d1d","datavalue":{"value":{"text":"Degree-preserving spanning trees in small-degree graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1579547$E6E4D155-23E0-4840-8C0C-28F4EE132F78","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9da6050a60c36942f0511c99a5abd472870c7c9a","datavalue":{"value":"0965.05035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579547$A8D31665-D84F-46E9-8216-99380782F06A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"01cde6e26365c7a4e2697f870548f809571f5756","datavalue":{"value":"10.1016/S0012-365X(00)00005-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579547$DDE1DFCE-D56B-4320-BF7C-620DCADF2063","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"efc35cf3e0639840fea360bd5e9b46c46abc9a77","datavalue":{"value":{"entity-type":"item","numeric-id":169283,"id":"Q169283"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579547$D0A91529-822B-48DD-B164-BEF4B4E9C33D","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":"Q1579547$8414A16E-003B-43A8-AD95-FDC27C1FDD57","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f0acde37fcd58040256bc107f747232cd94fa270","datavalue":{"value":{"time":"+2001-08-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1579547$53F0763F-584B-4EF8-95C5-34D5CE7E0345","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a224fffd71a7cc415199cf6983d3f038c90c105f","datavalue":{"value":"The degree-preserving spanning tree problem is to find, in a given connected graph \\(G= (V,E)\\), a spanning tree \\(T= (V,F)\\) with maximum number of vertices of the kind that all edges of \\(E\\) incident with such vertices belong to \\(F\\). The corresponding decision problem is denoted by DPST. The paper shows that the DPST problem is NP-complete for (1) bipartite planar graphs in which each vertex has degree at most 5; (2) planar graphs in which each vertex has degree at most 4; and (3) planar graphs in which each vertex has degree at most 3.    Moreover, the paper establishes relations of the DPST problem to the Steiner problem in graphs and the feedback vertex set problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579547$077BCE78-E63C-43F8-979E-6E73811332A3","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1b54857edcab7426c17c1bfaeb67b1f001fa1741","datavalue":{"value":{"entity-type":"item","numeric-id":587985,"id":"Q587985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1579547$643DBFD3-D2F7-4DF9-8355-40D63ACD76C1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579547$8130AD6D-F605-44E4-A2BD-3E136DACFDDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579547$EEC667DB-D8A7-4F2C-B173-5A10EEC06E24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579547$44D31633-CC0B-4407-A6DB-974A037E80BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579547$ACA42EDC-9A43-4164-A416-E7791F2DC92D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"82bb82c9cb1bff5e5a1b13a5dafbc15fa3fcf911","datavalue":{"value":"1506817","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579547$73CA2A4F-CFF8-46BB-A953-F6E37413F709","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579547$288A2AAA-1E14-461E-89A1-508C44836AE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579547$7D42DE9C-8EBC-4540-9480-4E782AB6CF96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c28b74bc2c5a39e87ba309ceaac02c298f82e24","datavalue":{"value":"Steiner problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1579547$BF7822F5-6DE9-44D0-8536-AC14B6D98B2B","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":"Q1579547$BABED38A-C376-4933-A279-39ADDDA20837","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"710a393979a214fdcb1618c7f67fd68972892909","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00005-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1579547$4EC2615B-1E09-47B1-9933-B2CD6E80205D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3c2d27105c1adfb39b43c095ea357d8ba38983ad","datavalue":{"value":"W2058281654","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579547$54F51109-00F1-4235-BD8B-36882B0226C6","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"a1fc95a3b1543d0bfcda6f2e52ecca28820a400e","datavalue":{"value":"Q127481587","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1579547$990A1955-3404-45D5-9A43-7CBD8782C266","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d75afffdb86b401fcebdc8d867539f87a13b4e57","datavalue":{"value":{"entity-type":"item","numeric-id":2342618,"id":"Q2342618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6c2fdfeaa43e1769ce72d0799adc598bb47a87e0","datavalue":{"value":{"amount":"+0.92132443","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579547$DDECA6DF-ECBE-4617-8BFE-9442F0EF0A4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"016267c5f9219322bb2afb374a4c1c8bb65db414","datavalue":{"value":{"entity-type":"item","numeric-id":452956,"id":"Q452956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a39422639123ea55cde57a62c94748fdd990f25a","datavalue":{"value":{"amount":"+0.9088726","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579547$A17D3B63-7CD1-43B2-A5A3-44DB1D808D95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7034f0507d7926165bfdb1b8b3b2b6b96dae3266","datavalue":{"value":{"entity-type":"item","numeric-id":968216,"id":"Q968216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b8751aa4c1ff521b2fbeb2bcca81316d322b48a9","datavalue":{"value":{"amount":"+0.9066161","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579547$89B01715-EE71-4DB6-AD15-FFE0BB904B80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd66ddc2bbb8553bdf5d258a016fcefcc53bb559","datavalue":{"value":{"entity-type":"item","numeric-id":3656869,"id":"Q3656869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6641b35d77692cc00871e752e604ddf19a60c6ce","datavalue":{"value":{"amount":"+0.9035909","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579547$F32F0EFB-81DF-40C3-BD9B-86B3C9DB640A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1afd4f54a5ba41b825c539ec6d5adc8775907382","datavalue":{"value":{"entity-type":"item","numeric-id":3057180,"id":"Q3057180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a69462bb72d54a692b7b92c2bc111cf99b1f453e","datavalue":{"value":{"amount":"+0.9028835","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579547$501102CA-0064-48A7-8D44-FAC94DC40CA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f5a64bda78e58054a5c3fe979a47eb4544cdc20","datavalue":{"value":{"entity-type":"item","numeric-id":1028423,"id":"Q1028423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dcf272d03d1c67c93d946fda67c7ff036f5d23cc","datavalue":{"value":{"amount":"+0.9021554","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579547$31ACA8CD-92CC-4D25-8278-1DB005463927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34c6ba4717a199791b253eaf1c4c1b6a29bf0d8a","datavalue":{"value":{"entity-type":"item","numeric-id":5154596,"id":"Q5154596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e91574b4a4791abe2c2d9a05719173dc139b1f1","datavalue":{"value":{"amount":"+0.90073407","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579547$36ECE5BE-29F1-47CC-A501-7CE77412E917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a814d3c56f5330f756a5f32bae3d06f374bc19dc","datavalue":{"value":{"entity-type":"item","numeric-id":2144593,"id":"Q2144593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae3d24c98e18b90a058e463b25cda2b266d51225","datavalue":{"value":{"amount":"+0.9002237","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579547$4D28D03B-7D88-4C6F-8D73-778DB5146F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c90aa4f0f7added4e4a467d0d61931828debce52","datavalue":{"value":{"entity-type":"item","numeric-id":1693164,"id":"Q1693164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dcf142a688f846e32be4eaa6c24e2bd01fab291","datavalue":{"value":{"amount":"+0.8983648","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579547$3D3032EE-923F-47F9-A4FB-430FAFCB64E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"000d4cb84acfbff4d9b982dd47b3e96e4628e424","datavalue":{"value":{"entity-type":"item","numeric-id":4877523,"id":"Q4877523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4fe031316e7a6622f3a5ae86dc1bc3555c86ad19","datavalue":{"value":{"amount":"+0.89755356","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1579547$CE8DD977-5622-437B-836B-70834F2BA5B0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Degree-preserving spanning trees in small-degree graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Degree-preserving_spanning_trees_in_small-degree_graphs"}}}}}