{"entities":{"Q414465":{"pageid":416232,"ns":120,"title":"Item:Q414465","lastrevid":61672326,"modified":"2026-04-11T00:52:55Z","type":"item","id":"Q414465","labels":{"en":{"language":"en","value":"Max-leaves spanning tree is APX-hard for cubic graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6033184"}},"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":"Q414465$0C19C757-D1BF-4706-99AE-1C193289C82F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b0bb66457b2ec155be691188ef5ac0aa70be95a0","datavalue":{"value":{"text":"Max-leaves spanning tree is APX-hard for cubic graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q414465$EA604EB5-CD22-478D-8ADE-135DC25CC4AF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b6165cb9ed8a1d1f82623ee22ec714f8382b6a01","datavalue":{"value":"1246.68121","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q414465$AF440B0B-7EFA-4A44-AC30-B9B7DB730C0E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"54aef55090a96c8e785afe18ef049813d4edd9d7","datavalue":{"value":{"entity-type":"item","numeric-id":392172,"id":"Q392172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$57727F9C-125E-410E-9622-63E868FFD43E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0a33251796f18919242eb286ef1f888e5d6e79da","datavalue":{"value":{"entity-type":"item","numeric-id":350720,"id":"Q350720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$C3E9F834-81B8-408D-86A9-D0F8E6245FE4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ebad7c55eb31a5728be157b82e80bb61556d824d","datavalue":{"value":{"time":"+2012-05-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":"Q414465$8579FD80-4A66-4995-889B-CAB85A55B935","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d2a4f8637a13e8e76055d8dd8350f16c474adb99","datavalue":{"value":"MaxLeaf is the problem of finding a spanning tree with a maximum number of leaves in a connected graph. \\textit{R. Solis-Oba} [Lect.\\ Notes Comput. Sci. 1461, 441--452 (1998; Zbl 0932.68069)] presented a 2-approximation algorithm for MaxLeaf. \\textit{P. Bonsma} and \\textit{F. Zickfeld} [SIAM J.\\ Discrete Math.\\ 25, No.\\ 4, 1652--1666 (2011; Zbl 1237.05041)] gave a 3/2-approximation algorithm for the restriction to cubic graphs. \\textit{G. Galbiati}, \\textit{F. Maffioli} and \\textit{A. Morzenti} [Inf. Process. Lett. 52, No. 1, 45--49 (1994; Zbl 0942.68647)] showed that MaxLeaf is APX-hard in general. Here the author shows that MaxLeaf is also APX-hard for cubic graphs, and so is the related problem Minimum Connected Dominating Set when restricted to cubic graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q414465$096AC4A2-0207-4175-A830-E670307ADBFD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q414465$70C949B8-A3E2-4331-81A4-666FE89A0E3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q414465$728FE890-DA1F-4455-ADA4-77E7D9502143","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q414465$073E6E29-3B21-4C34-B93C-E059CAA18BC6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5030f21222fc3ddd4d5854dc004161a8c5e99c2a","datavalue":{"value":"6033184","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q414465$30907AFC-0743-495A-94F0-B7D048DD8529","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eee669f83776c6ddcb60da5dcaa9813c9f6b11d9","datavalue":{"value":"maximum leaf","type":"string"},"datatype":"string"},"type":"statement","id":"Q414465$7017F0C5-4FDB-400E-8C9D-474279C8F278","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d07dde1a5d56cb0a0007c51b69fad6ef46044411","datavalue":{"value":"minimum connected dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q414465$0DF4CBC0-52AB-4107-8130-56E516F986DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"893fc4251dd98f99b23cbfacad1af41e79acd44e","datavalue":{"value":"APX-hard","type":"string"},"datatype":"string"},"type":"statement","id":"Q414465$F0BD9054-0BDD-4580-820B-9402D32A2756","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q414465$A56E5B9B-0C76-4352-8D97-925ADFCCFF9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e01f33e43354d516b8d6e654c1ded76a55047726","datavalue":{"value":"cubic graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q414465$F67B8BA1-EEB0-4E8E-A2E5-F361BBAC6C40","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":"Q414465$0FAB366E-48E5-4087-A01B-A72CE54FE711","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"353d231076bb3896139f38ecf86dac7f0e8edfda","datavalue":{"value":"https://doi.org/10.1016/j.jda.2011.06.005","type":"string"},"datatype":"url"},"type":"statement","id":"Q414465$C8E5A75A-96C1-4B4D-8535-1830B40FF571","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9d7f639e73d60bb1924c03bd281c31d13b51824f","datavalue":{"value":"W2964217904","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q414465$13AD0E17-C1B8-44E1-B08C-700BD6CA7F38","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"44f44a76b5719daa58c59d178eeffb178e71bb9e","datavalue":{"value":{"entity-type":"item","numeric-id":1566710,"id":"Q1566710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$098693A9-F475-47C8-BE3C-60C7F0BBA58C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed97d9cb381fa44bbd6ac9207fd7e4aa47354791","datavalue":{"value":{"entity-type":"item","numeric-id":3158513,"id":"Q3158513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$DB28E505-E7E9-4A98-B7DF-6AE18687E984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27d91ad1b485a4b515c7fdd7a683b79b2fd0a3f4","datavalue":{"value":{"entity-type":"item","numeric-id":3541089,"id":"Q3541089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$46243FF6-5BB5-4755-9DAD-D0FE6004DC66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8cf2e82a7aa5a4be1562606e08487a66bdee812","datavalue":{"value":{"entity-type":"item","numeric-id":5302044,"id":"Q5302044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$B657417A-D302-45CE-8961-067C2DFC28A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"adcf4d6c1b542cae75593c3982439cdd36790622","datavalue":{"value":{"entity-type":"item","numeric-id":5458557,"id":"Q5458557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$FC4AA311-92DA-4F71-A53D-7B862EDE7077","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f044a504878d1c9af09180e24129e23a0961f14b","datavalue":{"value":{"entity-type":"item","numeric-id":5443382,"id":"Q5443382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$20F5841F-3824-469B-8869-E66915F8D4AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3abcb9880598b91ae38c27b68318870b98b24df","datavalue":{"value":{"entity-type":"item","numeric-id":3656853,"id":"Q3656853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$D6F7FFE0-6DE3-44CD-80E3-1DB7BDE22532","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59f80f6e19275125de4f8e2f83f2df184481d4ef","datavalue":{"value":{"entity-type":"item","numeric-id":4342632,"id":"Q4342632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$E8A69DE2-F703-4147-B75A-F4FC1B0CCB39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37f5ecc0ce53f07a6cb11c6fca774fa9ac0303b6","datavalue":{"value":{"entity-type":"item","numeric-id":2930326,"id":"Q2930326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$E903AE95-47DE-4DC2-991F-011C48F29A97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6dceea2c0039c51ef0da7d93afbc5233b4aa5f9","datavalue":{"value":{"entity-type":"item","numeric-id":958203,"id":"Q958203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$35DED516-5AFE-4C3C-A658-65414315B07E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71542908e9fad76674adf735afe61192d9d61ebe","datavalue":{"value":{"entity-type":"item","numeric-id":1336751,"id":"Q1336751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$65B60173-B8BE-4509-9799-3BF5142E7997","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58dd170f3e55c0ab656c9ac0c3824e871f0d9f9c","datavalue":{"value":{"entity-type":"item","numeric-id":1196990,"id":"Q1196990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$9F2D8B18-31FF-46C3-8DDD-290D3AF37B92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cf8946b42a94ee2a262ea78b4fc83a36aec3ea5","datavalue":{"value":{"entity-type":"item","numeric-id":1386346,"id":"Q1386346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$F86F199D-436C-40AD-9E49-0FC9AF516A87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5771df2e63e94f541a65a02326887c8046e85fe5","datavalue":{"value":{"entity-type":"item","numeric-id":3360890,"id":"Q3360890"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$546BE8D0-D836-416E-B1C4-2FC1A670E95B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2961ec15a2e6a7b515a6b03c746dbf7f60c6d1e","datavalue":{"value":{"entity-type":"item","numeric-id":3596725,"id":"Q3596725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$B745F76A-165A-4E83-AA18-00F0353777C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b0b314152ed6376afac28db44d6c346e11f3147f","datavalue":{"value":{"entity-type":"item","numeric-id":4411401,"id":"Q4411401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$3874DE6D-BD72-48DD-B6BF-0B0DA050F6A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cc60e8ccb633da0914f96cd1cb78aed9963f75f","datavalue":{"value":{"entity-type":"item","numeric-id":1223319,"id":"Q1223319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$1AB00643-CF2A-4DBB-9214-458013ABC74A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c471e69923d527b115e8d87bd1f8dc46929dd2b2","datavalue":{"value":{"entity-type":"item","numeric-id":4217304,"id":"Q4217304"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$0BE23C0B-6BD8-4A39-94B1-F3D6C82D999A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce6133d293bb8bfa149948ffdc9b0f276ef45523","datavalue":{"value":{"entity-type":"item","numeric-id":1186548,"id":"Q1186548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$ABD57304-40F5-4782-8D37-7AE26C9D71DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7932a4fd6df411945cadd5651b399456800497c","datavalue":{"value":{"entity-type":"item","numeric-id":706637,"id":"Q706637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$2129B168-4420-498A-814B-934C12F47898","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd81c9091ae3da03281478f668fda454209e2edb","datavalue":{"value":{"entity-type":"item","numeric-id":4252040,"id":"Q4252040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q414465$F255A8F4-8B32-4EC3-BC41-996490B28DFD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0fe3a872900ff70baade6e56dc91d4b105b5c82f","datavalue":{"value":"10.1016/J.JDA.2011.06.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q414465$8D09F0D7-9821-41A6-92EB-942D3A4102EF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c7a8e6ea1d057209b07b6ab31d1a1b6f046c9839","datavalue":{"value":{"entity-type":"item","numeric-id":5443382,"id":"Q5443382"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e4c94bfe4faae16fed7cf19c1e18cacc2fa1c06","datavalue":{"value":{"amount":"+0.8981676697731018","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":"Q414465$F516DF93-3452-4DF2-82C5-5C7A8EA00AE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d5744d8544ca00395f4d0094989e64887b028028","datavalue":{"value":{"entity-type":"item","numeric-id":5302044,"id":"Q5302044"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a2cfcd6470a97fd08b9ba6181f1b823d9b49f260","datavalue":{"value":{"amount":"+0.8907397389411926","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":"Q414465$C12B8E50-E46D-444A-A991-1AC80D32BB38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02a5016f9b8a9efa54ce42a2a741860b1f30c36e","datavalue":{"value":{"entity-type":"item","numeric-id":3225144,"id":"Q3225144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3d95cac378a57384b55009be18341d9431f2447","datavalue":{"value":{"amount":"+0.8899510502815247","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":"Q414465$D7B6181F-15BD-44A2-9134-C26B075E63C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"431a31ef429ad4a32599c4300ecb9801ac5f635f","datavalue":{"value":{"entity-type":"item","numeric-id":4411401,"id":"Q4411401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"451a1a05723b381829dcedf3cc0512cbb780cf50","datavalue":{"value":{"amount":"+0.8719050288200378","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":"Q414465$FFA5BA76-130E-4525-8BCA-B9FD787D2465","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bbe03cc6f03eac75cd099b724554e40ee611e8c8","datavalue":{"value":{"entity-type":"item","numeric-id":264582,"id":"Q264582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85ac523c43cb245edbb2b1b1c3a910098f13beff","datavalue":{"value":{"amount":"+0.8524157404899597","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":"Q414465$F195D229-87FE-4280-AF1D-7F6A6CAE41B1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Max-leaves spanning tree is APX-hard for cubic graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Max-leaves_spanning_tree_is_APX-hard_for_cubic_graphs"}}}}}