{"entities":{"Q5918569":{"pageid":8049419,"ns":120,"title":"Item:Q5918569","lastrevid":54445520,"modified":"2026-01-26T20:14:00Z","type":"item","id":"Q5918569","labels":{"en":{"language":"en","value":"Upper and lower bounds on approximating weighted mixed domination"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7619410"}},"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":"Q5918569$CD33EEAD-DCF4-4E44-84BE-D0544E04D5A6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b198a9cdff3a7c3dbddfb253a24239f73ddc4641","datavalue":{"value":{"text":"Upper and lower bounds on approximating weighted mixed domination","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5918569$496A5B11-0858-4B9A-8D28-FCE5339163EF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8bb48d97aa42377c51cb11f373ef4c652a1af855","datavalue":{"value":{"entity-type":"item","numeric-id":255261,"id":"Q255261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$18D6ED7C-6859-4706-94E5-1D6E975EECCB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$1CDF7B13-8634-47CA-B259-B976C22B122B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bbd7a4f9b483e0e9b01f79a913d4946a9bd0bf2b","datavalue":{"value":{"time":"+2022-11-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5918569$333A8C80-4E4A-4F5F-A88B-E8E97F643ACE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e6890c8ee43cc6f5f9abfd0379404d2aaad7444d","datavalue":{"value":"This paper studies the complexity of the weighted mixed domination problem, where all edges have a weight \\(w_e>0\\), and all vertices have a weight \\(w_v>0\\). This problem asks for a subset of vertices and edges of a graph \\(G=(V,E)\\) like \\(D\\subseteq V\\cup E\\) with minimal total weight where every edge or vertex not in \\(D\\) is either adjacent or incident to some vertex to an edge in \\(D\\). It is known that this problem is NP-hard. This paper extends the results by showing that \\begin{itemize} \\item[1.] this problem is \\(2\\)-approximable if \\(w_e\\geq w_v\\) \\item[2.] this problem is inapproximable within ratio 1.3606 unless \\(\\mathrm{P = NP}\\) if \\(w_e\\geq 2w_v\\) \\item[3.] this problem is inapproximable within ratio 2 under the UGC \\item[4.] this problem is inapproximable within ratio \\((1- \\varepsilon )\\ln|V|\\) unless \\(\\mathrm{P = NP}\\) for any \\(\\varepsilon > 0\\) if \\(w_e<w_v\\) \\end{itemize} Note that the unweighted mixed dominating set problem has a simple 2-approximation algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918569$61D4C1FB-661E-457B-A5AA-576954385246","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6c1d39d6f200578316757400ebc308169220aec9","datavalue":{"value":{"entity-type":"item","numeric-id":2093878,"id":"Q2093878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$52F0A09E-6542-45A7-9EE1-76FDB349F202","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a4228d21095b3348e9ea20aa0b63610107aad8cc","datavalue":{"value":"68W25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918569$98637AAB-B851-413F-B90D-7FE26C9BB232","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918569$787257A4-E45F-4B89-821E-01B31C750D07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918569$A953342C-2ECF-450C-B338-F5795C523193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918569$ED10BDC4-3B5B-4EA3-A240-0EAE277BCC08","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"623b86e4e3a8b37dccddd07ee83eb2004d65ac9a","datavalue":{"value":"7619410","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918569$90467B22-A648-4F02-B454-129EA50B9A63","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cc4837877785b4675d8ac1c6d4c911bcaf794e13","datavalue":{"value":"approximation algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918569$A3238163-A7D4-4C1C-8FFB-34346178B9B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51f95efbd0445c23f397467c5e509da28dd67bbc","datavalue":{"value":"inapproximability","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918569$D27F98CF-9B19-4257-A2EA-A38BA26AF42B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9ebc0d32681f771c3da8fa3ac4ae96e2f1d8e69","datavalue":{"value":"mixed dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918569$660E1134-2BA7-4918-B12A-4001D0615FF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aac385c43cc6d982a9dd1fbfee8ab2754a681c11","datavalue":{"value":"vertex cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q5918569$933E65FC-8698-4D3A-BE8D-366161C78BC4","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":"Q5918569$EC5E3363-CE0F-465F-A453-910183B47624","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"846a8042ff42e87a59e1b167b391dce531b03ab8","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2022.10.033","type":"string"},"datatype":"url"},"type":"statement","id":"Q5918569$9B712F97-3A18-4AF3-BB53-150536D2BBF5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"25561eb4bdb4db11e47d9b45d97fc9584a2d4375","datavalue":{"value":"W4308357971","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918569$DA0E7509-C9D9-49BA-80D2-67CFF01B8E2A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a91048c4d5b6ad348ce72b3909d4d2feef0f06c","datavalue":{"value":{"entity-type":"item","numeric-id":4154591,"id":"Q4154591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$047A8F91-AEF3-44E7-81D0-5F645996E490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3183512a59174fa963d7a60ee2b593558f89cbe","datavalue":{"value":{"entity-type":"item","numeric-id":1198645,"id":"Q1198645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$04D9B81D-0F27-458E-90C7-3CC333DE0096","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a085110f25069146b2ebfef0f9dedd979d8f36a1","datavalue":{"value":{"entity-type":"item","numeric-id":3579199,"id":"Q3579199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$5C0D6A7A-D10F-4BD7-B7A1-2480837BD4AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d00a694d0f3c2004e75a830c958cf154ee868c4d","datavalue":{"value":{"entity-type":"item","numeric-id":5259598,"id":"Q5259598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$C885C320-FD1F-4F39-BCB7-634252048429","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"da9c4a389e7b93c250afffaf533e9c0366c4e836","datavalue":{"value":{"entity-type":"item","numeric-id":2345984,"id":"Q2345984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$3AE1CB7D-D69E-4C1A-9F32-CFF1F39B1735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddaffef330ee827a6215588ad1a43162a97d617f","datavalue":{"value":{"entity-type":"item","numeric-id":1602689,"id":"Q1602689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$A0388E74-F8C0-485B-900D-2CCFF6490A16","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":"Q5918569$7522D5D9-AA1A-484C-90BD-08D18E166689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33aeb2afbda49246925bc369cbd5f6966f86a7eb","datavalue":{"value":{"entity-type":"item","numeric-id":3504806,"id":"Q3504806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$24C1DBA1-D9D3-41AF-A0D2-2F079BE5CE06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d60c9e7ebaed93a14c443423d2ee67e909f62ff4","datavalue":{"value":{"entity-type":"item","numeric-id":4368728,"id":"Q4368728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$D5A0BF7F-98F0-4F31-BBFE-40128B3FD875","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6886ba90c5b25f06766b8495ec24fd320596293a","datavalue":{"value":{"entity-type":"item","numeric-id":810066,"id":"Q810066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$784EF14D-C612-44D2-9A76-238CAB9AD9B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14374675cce9e2d17fed68537000e88c25104889","datavalue":{"value":{"entity-type":"item","numeric-id":1687931,"id":"Q1687931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$B6ABEEE7-7F83-41FB-9B4F-8A3CBEACED07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a567a0bd5149009c58baa277d371437f0fed769","datavalue":{"value":{"entity-type":"item","numeric-id":1213733,"id":"Q1213733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$A444FA25-89B3-4215-B7E4-8F5306CA8C40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0b5980a020f792e65e377e840331a397c046736","datavalue":{"value":{"entity-type":"item","numeric-id":2475406,"id":"Q2475406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$09C4C08C-5FE6-4BEC-8153-2F761D35862D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7e4d23fac8971ec0e72a17edbe4d6d748f2597c","datavalue":{"value":{"entity-type":"item","numeric-id":1945934,"id":"Q1945934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$9BCED399-9C85-4E2D-8177-3491E9B59E56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f73d591551f97c06203b9dc1822ba12bfad4538a","datavalue":{"value":{"entity-type":"item","numeric-id":1283793,"id":"Q1283793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$9F870EB5-D1C7-4B18-9E8C-5CE19A041B10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c72e5144fc35b1673d6188020da4e95cfd8a1344","datavalue":{"value":{"entity-type":"item","numeric-id":4766816,"id":"Q4766816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$B7A3ECD6-09E5-45D7-9442-2E317BA6C620","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f124f41fb4338c9a1a9b4b869707afb9a6755a72","datavalue":{"value":{"entity-type":"item","numeric-id":5898481,"id":"Q5898481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$41AF7981-FDA5-4EAE-9CB3-C9FDD9410731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"028284077539ceccf1a5bdf303f527018de8ebb0","datavalue":{"value":{"entity-type":"item","numeric-id":392035,"id":"Q392035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$D400FB24-7155-49F2-BDF6-49B2F6A7AF2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cc200e2bbfe40b87f5c815caf64de20fd253376","datavalue":{"value":{"entity-type":"item","numeric-id":388085,"id":"Q388085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$C8760E6A-3221-4398-84F9-E3B025A1842A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"389c996862e2e5ca571ae15f0ad30e059de0b679","datavalue":{"value":{"entity-type":"item","numeric-id":2310753,"id":"Q2310753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$B03C8006-0781-497C-934E-555499DD05B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e7032db704a3c4fcea69481a5580e82a7d02eda","datavalue":{"value":{"entity-type":"item","numeric-id":3903038,"id":"Q3903038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$88F020C7-EA26-45D6-8CC4-B0CC9B1B6D24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6e9e9d0d93ad0b3460f6ccdf921150d74adaf93","datavalue":{"value":{"entity-type":"item","numeric-id":533883,"id":"Q533883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5918569$9AC450F7-4AE6-4C20-9091-0CCB88E2ACA7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cbd057674b2e669c3e9bd3303930c7219ffa447c","datavalue":{"value":"10.1016/J.TCS.2022.10.033","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5918569$49EF531B-95C0-47D4-AECE-AA90C2665E5F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1fd3dc83774352bdd5f2c0cf7cd8a9d7cf02e84a","datavalue":{"value":{"entity-type":"item","numeric-id":5952320,"id":"Q5952320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ab1df814530c385132e4a41e12f5c022ecffde50","datavalue":{"value":{"amount":"+0.8198561668395996","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":"Q5918569$EDB989E8-14DD-4EA7-9FF7-9F3909E51346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41c480411e8e5661448476b4c8b32b9e172aa3c2","datavalue":{"value":{"entity-type":"item","numeric-id":2753930,"id":"Q2753930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80939672b79a983ad52d32b2a73503da1051bc06","datavalue":{"value":{"amount":"+0.8173427581787109","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":"Q5918569$90561647-403B-4550-9A24-4DE2A3ABDA78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"480e93ccc77ce1e3a314993cbcd6ad9bae9c9180","datavalue":{"value":{"entity-type":"item","numeric-id":2369972,"id":"Q2369972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fba063e24dd849c1efdc77044111c01146944fc0","datavalue":{"value":{"amount":"+0.8170768618583679","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":"Q5918569$38CB5DD4-77CF-471A-949C-9CE66A6FD507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4f0cbc0d41ce38417d6ec1b048064b6b17257e8","datavalue":{"value":{"entity-type":"item","numeric-id":1602689,"id":"Q1602689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e261af28185f63aaec78d31981c4043a72e88405","datavalue":{"value":{"amount":"+0.8004403114318848","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":"Q5918569$46E88E33-3F96-463A-AB59-B44BBDF4264C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aecf79d53ff5c9191210e3376daa6fb03a020b94","datavalue":{"value":{"entity-type":"item","numeric-id":1603390,"id":"Q1603390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c88dea9e92f5f5af61e162c2f085518df4922909","datavalue":{"value":{"amount":"+0.7941253185272217","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":"Q5918569$EA5C82D7-26B2-4816-B5B2-E9ABA1584776","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5918569","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5918569"}}}}}