{"entities":{"Q6157416":{"pageid":13292043,"ns":120,"title":"Item:Q6157416","lastrevid":47849722,"modified":"2026-01-02T21:10:58Z","type":"item","id":"Q6157416","labels":{"en":{"language":"en","value":"Algorithmic results on locating-total domination in graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7684695"}},"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":"Q6157416$B92623A4-41C9-4750-90DC-A29B61E85144","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ee7cdd966a063e4ec37a5170a49d0a07b7e80c70","datavalue":{"value":{"text":"Algorithmic results on locating-total domination in graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6157416$091BF986-F9BC-4F51-BC99-AF770FB51E39","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7ec95d0ae7c57b3e7a453bc3f18ab0284a93378d","datavalue":{"value":"1514.05124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6157416$FA304C47-9F7E-4491-AEF9-772DDA1DECA8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"44991811c2e2467c2035bdce224adb5066686a62","datavalue":{"value":{"entity-type":"item","numeric-id":265717,"id":"Q265717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6157416$0622F80B-7784-47C9-BA63-C924BF0CA611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0a42bc8631f1cc6890cb50caae2de6b67edb86b0","datavalue":{"value":{"entity-type":"item","numeric-id":265716,"id":"Q265716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6157416$975F5AA7-01F4-430E-B9FC-E9D1F0B423CA","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":"Q6157416$AC2174D9-6C74-44E1-AC33-C080E89918E7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"19017a32ebba0dcced03911c093c22569ec7a3f1","datavalue":{"value":{"time":"+2023-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":"Q6157416$3CD21E5C-87CE-4435-B884-79C3A1D06C52","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"48bbf2ac316df682e652a092fd025948e9294705","datavalue":{"value":"A dominating set (DS) of \\(G\\) is a set \\(D\\subseteq V\\) such that each vertex in \\(V\\setminus D\\) is adjacent to at least one vertex in \\(D\\). A total dominating set (TDS) of \\(G\\) is a set \\(D\\subseteq V\\) with the property that each vertex in \\(V\\) is adjacent to at least one vertex in \\(D\\). A locating-dominating set (LDS) of \\(G\\) is a subset \\(D\\subseteq V\\) such that \\(D\\) is a DS of \\(G\\) and \\(N(u) \\cap D\\neq N(v)\\cap D\\) for each pair of distinct vertices \\(u\\) and \\(v\\) in \\(V\\setminus D\\). A locating-total dominating set (LTDS) of \\(G\\) is a subset \\(D\\subseteq V\\) such that \\(D\\) is both TDS and LDS of \\(G\\). The smallest size of an LTDS of \\(G\\) between all LTDSs of \\(G\\) is called the locating-total domination number of \\(G\\), denoted by \\(\\gamma_L^t(G)\\). The Locating-Total Dominating Set problem is the problem of computing an LTDS \\(D\\) of a given graph \\(G\\) with \\(|D|=\\gamma_L^t(G)\\).   The authors prove that the decision version of the Locating-Total Dominating Set problem is NP-complete for circle graphs, undirected path graphs, and graphs of separability at most 2. Also, they give a \\((2 \\ln|V|+1.7)\\)-approximation algorithm for computing a minimum LTDS of a given graph \\(G\\) and prove that the problem of computing a minimum locating-total dominating set is APX-complete for graphs of degree at most 4. Finally, they propose a linear algorithm for computing the locating-total domination number of trees.","type":"string"},"datatype":"string"},"type":"statement","id":"Q6157416$69F7FE2A-1D90-4780-80EA-DE7FF2CADEA9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3e5241478eb111c3d7b9249ceb02ff850b9ad819","datavalue":{"value":{"entity-type":"item","numeric-id":277497,"id":"Q277497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6157416$D33D95EE-9630-4F2C-A77D-90CFEB8D2B49","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6157416$875A8204-0CF9-44E8-A053-72FA977E1519","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6157416$A448EE6F-E84F-4CF4-9488-89F3FDA50CD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6157416$D86CB2F0-272C-4D2E-A0A8-798FF2AD1FB5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ef065eea86f6e44154404e754ccdff95cdb63676","datavalue":{"value":"7684695","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6157416$1B5459A4-DFD4-40DC-B542-B7A64232253D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q6157416$183FA990-9EA4-4CCE-BFA7-246D929529A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e3e2b36f8654bdf6002a16b999eae3f9e07088d","datavalue":{"value":"locating-total dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q6157416$7962530A-3474-43A9-9964-5C2780529775","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q6157416$65F0812B-5FEB-4923-A33C-A8B198E821F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48ddf43eca498c7e7087cd696beb82ea63925320","datavalue":{"value":"algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q6157416$4FC6D44F-919C-4CBC-9DA0-1D6E944B2AC4","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":"Q6157416$25B19E6C-D0BC-45A5-8B49-F0529A5EE966","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"77ebefd504476de8ec743314ad5db615dd953f07","datavalue":{"value":"https://doi.org/10.1016/j.dam.2023.03.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q6157416$98014A4E-42F5-45FD-919B-97C0076885F1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ee41cebd632944d23d26e55c1cb8ab44527644e8","datavalue":{"value":"W4327630313","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6157416$605E9B19-A36C-4F29-9353-725B23600FDE","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":"Q6157416$0B42674F-ACEC-46DB-A8A8-B2CE111935BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22d1973db283005ec57d81fef431bca226f261b9","datavalue":{"value":{"entity-type":"item","numeric-id":534338,"id":"Q534338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6157416$D63A4F03-E88C-43EA-864A-B7FD233FA450","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ab550fba1bb94ab208f5d59ab407a793a68d049","datavalue":{"value":{"entity-type":"item","numeric-id":415268,"id":"Q415268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6157416$8551B17A-1203-486A-BE5E-0257F755B778","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"765c4ab66609c05ad06f7aab5768669759e6118c","datavalue":{"value":{"entity-type":"item","numeric-id":2495911,"id":"Q2495911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6157416$5F4F4708-3970-42BC-BBBB-200C689AD14F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7a7ff3d680cbe31dd012aef5168b2bd3a510c7c","datavalue":{"value":{"entity-type":"item","numeric-id":442212,"id":"Q442212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6157416$4D924C17-335A-4160-AD6A-ABBA6F633142","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2ecebafd643daaeb953e3d29cb600f7ebea640","datavalue":{"value":{"entity-type":"item","numeric-id":456648,"id":"Q456648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6157416$F1E6E76D-88D6-4F41-A570-7B5FBA0511CD","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":"Q6157416$AC88CEB3-EA5F-4F85-91A9-960BD0A5C551","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef59647203c58ee1f83043f928eba109372c62e9","datavalue":{"value":{"entity-type":"item","numeric-id":1209148,"id":"Q1209148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6157416$EAEC159B-F2CB-4D21-8A60-054157A3C878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"102e00908e37867742c13b204cd9b07f16f77f1d","datavalue":{"value":{"entity-type":"item","numeric-id":2364093,"id":"Q2364093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6157416$83B964BA-D3B2-42A7-90E0-481A613EB607","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":"Q6157416$DBC7A0ED-89AA-4DBA-AD89-083FD0DB8CC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"128586845375b6590addb00dc387179668ac1d9f","datavalue":{"value":{"entity-type":"item","numeric-id":2333807,"id":"Q2333807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6157416$A74B500C-C681-40EB-8291-3374C12580E9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6b0d24a26f483f002a0ead729b92ec1fa7fb61cd","datavalue":{"value":"10.1016/J.DAM.2023.03.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6157416$D5B11451-FA54-4944-9C2F-26870248AE50","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2542292e261828f3923aafc111c322b2603b1507","datavalue":{"value":{"entity-type":"item","numeric-id":2333807,"id":"Q2333807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f3d3e41e7b01a4138e297a39786c1a50eb91e09","datavalue":{"value":{"amount":"+0.8823448419570923","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":"Q6157416$47CBEBC2-96C6-48EC-B4A1-18D4D44C8208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39b326b6571c37595c2fff45f82b901c89034bfc","datavalue":{"value":{"entity-type":"item","numeric-id":442212,"id":"Q442212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"64177eeba517e1a297483078862897aebd91dd8e","datavalue":{"value":{"amount":"+0.8448916077613831","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":"Q6157416$F110D95B-1C08-496F-8D0F-3E0816897DB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53ca9145c8a7dbec80222ea1936ce5bc954724d8","datavalue":{"value":{"entity-type":"item","numeric-id":2364093,"id":"Q2364093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2be69b7ec4562e2299a66ba1af149889173d57f","datavalue":{"value":{"amount":"+0.8329712748527527","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":"Q6157416$8A831740-1356-456E-B8A1-8C05922DEEF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"663da36b42d39765c685d13cb58d0cc9f122e511","datavalue":{"value":{"entity-type":"item","numeric-id":2282462,"id":"Q2282462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2f8d2f117347ef9cd30384d955967b72446549e","datavalue":{"value":{"amount":"+0.8302085995674133","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":"Q6157416$75AF3315-9971-4667-AE32-E8267AB0C917","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f228cc8e1f798f47e0d79ca1d394e53d16a1024","datavalue":{"value":{"entity-type":"item","numeric-id":4594211,"id":"Q4594211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08bc4a63d4584e1688c6e0b1268373d756045db6","datavalue":{"value":{"amount":"+0.8291671276092529","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":"Q6157416$BC64D20F-1202-4210-8051-852F1EF0743B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6157416","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6157416"}}}}}